Из Википедии, бесплатной энциклопедии
Перейти к навигации Перейти к поиску
Не путать с проблемой почтовой переписки .

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

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

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

Официальное заявление [ править ]

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

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

PCP и твердость аппроксимации [ править ]

Альтернативная формулировка теоремы РСР состояний , что максимальная доля выполнимых ограничений в задаче удовлетворения ограничений является NP-трудной для аппроксимации в пределах некоторого постоянного множителя.

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

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

где Φ - проблема удовлетворения ограничений над булевым алфавитом с не более чем K переменных на ограничение.

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

Доказательство [ править ]

Доказательство более слабого результата NP = PCP [n 3 , 1] дано в одной из лекций Декстера Козена. [3]

История [ править ]

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

Этимология названия "теорема PCP" [ править ]

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

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

История после первой теоремы [в 1990 году] [ править ]

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

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

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

Квантовый аналог теоремы PCP [ править ]

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

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

Заметки [ править ]

  1. ^ Инго Вегенер (2005). Теория сложности: изучение границ эффективных алгоритмов . Springer. п. 161. ISBN. 978-3-540-21045-0.
  2. ↑ Одед Гольдрайх (2008). Вычислительная сложность: концептуальная перспектива . Издательство Кембриджского университета. п. 405. ISBN 978-0-521-88473-0.
  3. Перейти ↑ Kozen, Dexter C. (2006). Теория вычислений . Тексты по информатике. Лондон: Springer-Verlag. С. 119–127. ISBN 9781846282973.
  4. ^ См препринт 2005, ЧПСК  TR05-046 . Авторитетная версия статьи - Dinur (2007) .
  5. ^ EATSC 2019 Гедель премии , извлекаться 2019-09-11.
  6. ^ а б Ито, Цуёси; Видик, Томас (2012). «Интерактивное доказательство того, что NEXP работает против запутанных пруверов». arXiv : 1207,0550 [ квант-ф ].
  7. ^ Hardesty, Ларри (2012-07-30). «MIT News Release: проблема теоретической информатики десятилетней давности рушится» . Офис новостей Массачусетского технологического института. Архивировано 02 февраля 2014 года . Проверено 10 августа 2012 . Интерактивные доказательства являются основой широко используемых в настоящее время криптографических систем, но для компьютерных ученых они не менее важны для понимания сложности вычислительных проблем. CS1 maint: обескураженный параметр ( ссылка )
  8. ^ a b Хардести, Ларри (31.07.2012). «Решается задача 10-летней давности в теоретической информатике» . Офис новостей Массачусетского технологического института. Архивировано 01 августа 2012 года . Проверено 10 августа 2012 . Дорит Ааронов, профессор информатики и инженерии Еврейского университета в Иерусалиме, говорит, что статья Видика и Ито является квантовым аналогом более ранней статьи о многопроверочных интерактивных доказательствах, которая «в основном привела к теореме PCP, а теорема PCP не вызывает сомнений. самый важный результат комплексности за последние 20 лет ». Точно так же, по ее словам, новая статья «могла бы стать важным шагом на пути к доказательству квантового аналога теоремы PCP, которая является основным открытым вопросом в квантовой теории сложности». CS1 maint: обескураженный параметр ( ссылка )
  9. ^ Натараджан, А .; Видик, Т. (октябрь 2018 г.). «Низкоуровневое тестирование квантовых состояний и PCP по квантовым запутанным играм для QMA». 59-й ежегодный симпозиум по основам компьютерных наук (FOCS) IEEE 2018 : 731–742. arXiv : 1801.03821 . Bibcode : 2018arXiv180103821N . DOI : 10.1109 / FOCS.2018.00075 . ISBN 978-1-5386-4230-6.

Ссылки [ править ]

  • Арора, Санджив ; Лунд, Карстен ; Мотвани, Раджив ; Судан, Мадху ; Szegedy, Марио (1998), "Доказательство проверка и твердость задач аппроксимации", Журнал ACM , 45 (3): 501-555, DOI : 10,1145 / 278298,278306.
  • Арора, Санджив ; Сафра, Шмуэль (1992), «Приближающая клика является NP-полной», в материалах 33-го симпозиума IEEE по основам компьютерных наук , 41 (1): 2–13.
  • Арора, Санджив ; Сафра, Шмуэль (1998), "Вероятностная проверка доказательств: Новая характеристика НП", Журнал ACM , 45 (1): 70-122, DOI : 10,1145 / 273865,273901.
  • Бабай, Ласло ; Фортноу, Лэнс ; Левин, Леонид ; Сегеди, Марио (1991), «Проверка вычислений в полилогарифмическом времени», STOC '91: Материалы двадцать третьего ежегодного симпозиума ACM по теории вычислений , ACM, стр. 21–32, ISBN 978-0-89791-397-3.
  • Бабай, Ласло ; Фортноу, Лэнс ; Лунд, Карстен (1990), «Недетерминированное экспоненциальное время имеет два интерактивных протокола», SFCS '90: Материалы 31-го ежегодного симпозиума по основам компьютерных наук , IEEE Computer Society, стр. 16–25, ISBN 978-0-8186-2082-9.
  • Динур, Ирит (2007), «Теорема PCP по усилению разрыва», Журнал ACM , 54 (3): 12 – es, doi : 10.1145 / 1236457.1236459 CS1 maint: обескураженный параметр ( ссылка ).
  • Файги, Уриил ; Гольдвассер, Шафи ; Ловас, Ласло ; Сафра, Шмуэль ; Szegedy, Марио (1996), "Интерактивные доказательства и твердость аппроксимирующих кликов" (PDF) , Журнал ACM , ACM, 43 (2): 268-292, DOI : 10,1145 / 226643,226652 , ISSN  0004-5411.