теорема PCP
Теорема в теории сложности вычислений

В теории сложности вычислений теорема PCP (также известная как теорема характеризации PCP ) утверждает, что каждая задача принятия решений в классе сложности NP имеет вероятностно проверяемые доказательства ( доказательства , которые могут быть проверены рандомизированным алгоритмом ) постоянной сложности запроса и логарифмической сложности случайности (использует логарифмическое число случайных битов).

Теорема PCP гласит, что для некоторой универсальной константы K , для каждого n , любое математическое доказательство для утверждения длины n может быть переписано как другое доказательство длины poly( n ), которое формально проверяемо с точностью 99% с помощью рандомизированного алгоритма , который проверяет только K букв этого доказательства.

Теорема PCP является краеугольным камнем теории вычислительной сложности аппроксимации , которая исследует неотъемлемую сложность разработки эффективных алгоритмов аппроксимации для различных задач оптимизации . Инго Вегенер описал ее как «самый важный результат в теории сложности со времен теоремы Кука » [1] , а Одед Голдрайх — как «кульминацию серии впечатляющих работ […], богатых новаторскими идеями». [2]

Официальное заявление

Теорема PCP утверждает, что

NP = PCP [O(log n ), O(1)],

где PCP [ r ( n ),  q ( n )] — класс задач, для которых может быть дано вероятностно проверяемое доказательство решения, так что доказательство может быть проверено за полиномиальное время с использованием r ( n ) бит случайности и путем чтения q ( n ) бит доказательства, правильные доказательства всегда принимаются, а неправильные доказательства отклоняются с вероятностью не менее 1/2. n — длина в битах описания экземпляра задачи. Отметим далее, что алгоритм проверки неадаптивен : выбор битов доказательства для проверки зависит только от случайных битов и описания экземпляра задачи, а не от фактических битов доказательства.

PCP и жесткость аппроксимации

Альтернативная формулировка теоремы PCP гласит, что максимальную долю выполнимых ограничений задачи удовлетворения ограничений NP -трудно приблизить с точностью до некоторого постоянного множителя. [3]

Формально, для некоторых констант q и α < 1 следующая задача обещания ( L да , L нет ) является NP-трудной задачей принятия решений:

  • L да = {Φ: все ограничения в Φ одновременно выполнимы}
  • L no = {Φ: каждое назначение удовлетворяет менее чем α-доле ограничений Φ},

где Φ — задача удовлетворения ограничений (CSP) над булевским алфавитом с максимум q переменными на ограничение.

Связь с классом PCP, упомянутым выше, можно увидеть, заметив, что проверка постоянного числа бит q в доказательстве может рассматриваться как оценка ограничения в q булевых переменных на этих битах доказательства. Поскольку алгоритм проверки использует O (log  n ) бит случайности, его можно представить как CSP, как описано выше с ограничениями poly ( n ). Другая характеристика теоремы PCP тогда гарантирует условие обещания с α = 1/2: если ответ на задачу NP — да, то каждое ограничение (которое соответствует конкретному значению для случайных бит) имеет удовлетворяющее назначение (приемлемое доказательство); в противном случае любое доказательство должно быть отклонено с вероятностью не менее 1/2, что означает, что любое назначение должно удовлетворять менее 1/2 ограничений (что означает, что оно будет принято с вероятностью ниже 1/2). Следовательно, алгоритм для задачи обещания сможет решить основную задачу NP, и, следовательно, задача обещания должна быть NP-сложной.

Как следствие этой теоремы, можно показать, что решения многих естественных задач оптимизации, включая максимальную выполнимость булевой формулы , максимальное независимое множество в графах и задачу о кратчайшем векторе для решеток, не могут быть эффективно приближены, если только P = NP . Это можно сделать, сведя задачу приближения решения таких задач к задаче обещания вышеуказанной формы. Эти результаты иногда также называют теоремами PCP, поскольку их можно рассматривать как вероятностно проверяемые доказательства для NP с некоторой дополнительной структурой.

Доказательство

Доказательство более слабого результата ⁠ ⁠ Н П ⊆ П С П [ н 3 , 1 ] {\displaystyle {\mathsf {NP}}\subseteq {\mathsf {PCP}}[n^{3},1]} приведено в одной из лекций Декстера Козена. [4]

История

Теорема PCP является кульминацией долгой линии работы над интерактивными доказательствами и вероятностно проверяемыми доказательствами. Первая теорема, связывающая стандартные доказательства и вероятностно проверяемые доказательства, — это утверждение, что NEXP ⊆ PCP [poly( n ), poly( n )], доказанное Бабаем, Фортноу и Лундом (1990).

Происхождение инициалов

Обозначение PCP c ( n ),  s ( n ) [ r ( n ),  q ( n )] объясняется в вероятностно проверяемом доказательстве . Обозначение является обозначением функции, которая возвращает определенный класс сложности. См. объяснение, упомянутое выше.

Название этой теоремы («теорема PCP»), вероятно, происходит либо от «PCP», что означает « вероятностно проверяемое доказательство », либо от упомянутой выше нотации (или от обоих).

Первая теорема [в 1990 году]

Впоследствии методы, использованные в этой работе, были расширены Бабаем, Лэнсом Фортноу , Левиным и Сегеди в 1991 году (Babai et al. 1991), Фейге, Голдвассером, Лундом, Сафрой и Сегеди (1991), а также Аророй и Сафрой в 1992 году (Arora & Safra 1992) для получения доказательства теоремы PCP Аророй, Лундом, Мотвани, Суданом и Сегеди в 1998 году (Arora et al. 1998).

Премия Гёделя 2001 года была присуждена Сандживу Ароре , Уриэлю Фейге , Шафи Гольдвассеру , Карстену Лунду , Ласло Ловасу , Радживу Мотвани , Шмуэлю Сафре , Мадху Судану и Марио Сегеди за работу над теоремой PCP и ее связью с трудностью аппроксимации.

В 2005 году Ирит Динур нашла значительно более простое доказательство теоремы PCP, используя расширительные графы . [5] За это она получила премию Гёделя 2019 года . [6]

Квантовый аналог

В 2012 году Томас Видик и Цуёси Ито опубликовали результат [7] , который показал «сильное ограничение на способность запутанных доказывающих вступать в сговор в многопользовательской игре». Это может быть шагом к доказательству квантового аналога теоремы PCP, поскольку, когда результат [7] был опубликован в СМИ, [8] [9] профессор Дорит Ааронов назвал его «квантовым аналогом более ранней статьи о многодоказательных интерактивных доказательствах», которая «в основном привела к теореме PCP». [9]

В 2018 году Томас Видик и Ананд Натараджан доказали [10] игровой вариант квантовой теоремы PCP при рандомизированной редукции. Он утверждает, что QMA ⊆ MIP ∗ [log( n ), 1, 1/2] , где MIP ∗ [ f ( n ), c ​​, s ] — это класс сложности квантовых интерактивных систем доказательств с несколькими доказывающими с f ( n )-битными классическими коммуникациями, а полнота равна c , а надежность — s. Они также показали, что гамильтонова версия квантовой гипотезы PCP, а именно локальная гамильтонова задача с постоянным зазором обещаний c − s является QMA -трудной, что влечет за собой игровую квантовую теорему PCP.

Гипотеза NLTS была фундаментальным неразрешенным препятствием и предшественником квантового аналога PCP. [11] Гипотеза NLTS была доказана в 2022 году Анурагом Аншу, Николасом Брейкманном и Чинмэем Нирхе. [12]

Примечания

  1. ^ Инго Вегенер (2005). Теория сложности: исследование пределов эффективных алгоритмов. Springer. стр. 161. ISBN 978-3-540-21045-0.
  2. ^ Одед Голдрайх (2008). Computational Complexity: A Conceptual Perspective. Cambridge University Press. стр. 405. ISBN 978-0-521-88473-0.
  3. ^ Арора, Санджив; Барак, Боаз (2009). Вычислительная сложность: современный подход (PDF) (черновик). Cambridge University Press.
  4. ^ Козен, Декстер К. (2006). Теория вычислений. Тексты по информатике. Лондон: Springer-Verlag. С.  119–127 . ISBN. 9781846282973.
  5. ^ См. препринт 2005 г., ECCC  TR05-046. Авторитетной версией статьи является Динур (2007).
  6. ^ Премия Гёделя EATSC 2019, получено 11 сентября 2019 г.
  7. ^ ab Ito, Tsuyoshi; Vidick, Thomas (2012). «Интерактивное доказательство с несколькими доказывающими для звука NEXP против запутанных доказывающих». 53-й ежегодный симпозиум IEEE по основам компьютерной науки, FOCS 2012, Нью-Брансуик, Нью-Джерси, США, 20–23 октября 2012 г. IEEE Computer Society. стр.  243–252 . arXiv : 1207.0550 . doi :10.1109/FOCS.2012.11. ISBN 978-0-7695-4874-6.
  8. ^ Хардести, Ларри (2012-07-30). "MIT News Release: 10-летняя проблема в теоретической информатике рушится". MIT News Office. Архивировано из оригинала 2014-02-02 . Получено 2012-08-10 . Интерактивные доказательства являются основой криптографических систем, которые сейчас широко используются, но для компьютерных ученых они так же важны, как и понимание, которое они дают в отношении сложности вычислительных задач.
  9. ^ ab Hardesty, Larry (2012-07-31). "10-летняя проблема в теоретической информатике рушится". MIT News Office. Архивировано из оригинала 2012-08-01 . Получено 2012-08-10 . Дорит Ааронов, профессор компьютерных наук и инженерии в Еврейском университете в Иерусалиме, говорит, что статья Видика и Ито является квантовым аналогом более ранней статьи об интерактивных доказательствах с несколькими доказательствами, которая "в основном привела к теореме PCP, а теорема PCP, без сомнения, является самым важным результатом сложности за последние 20 лет". Аналогичным образом, говорит она, новая статья "может стать важным шагом на пути к доказательству квантового аналога теоремы PCP, которая является основным открытым вопросом в квантовой теории сложности".
  10. ^ Natarajan, A.; Vidick, T. (октябрь 2018 г.). «Тестирование квантовых состояний с низкой степенью и квантовые запутанные игры PCP для QMA». 59-й ежегодный симпозиум IEEE по основам компьютерной науки (FOCS) 2018 г. стр.  731–742 . arXiv : 1801.03821 . Bibcode :2018arXiv180103821N. doi :10.1109/FOCS.2018.00075. ISBN 978-1-5386-4230-6. S2CID  53062680.
  11. ^ "О гипотезе NLTS". Институт теории вычислений Саймонса . 2021-06-30 . Получено 2022-08-08 .
  12. ^ Anshu, Anurag; Breuckmann, Nikolas P.; Nirkhe, Chinmay (2023). "NLTS Hamiltonians from Good Quantum Codes". Труды 55-го ежегодного симпозиума ACM по теории вычислений . стр.  1090–1096 . arXiv : 2206.13228 . doi :10.1145/3564246.3585114. ISBN 9781450399135. S2CID  250072529.

Ссылки

Получено с "https://en.wikipedia.org/w/index.php?title=PCP_theorem&oldid=1263192709#Quantum_analog"