Теорема PCP - PCP theorem

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

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

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

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

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

НП = PCP[O (журнал п), O (1)].

PCP и жесткость приближения

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

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

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

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

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

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

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

История

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

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

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

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

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

Впоследствии методы, использованные в этой работе, были расширены Бабаем, Лэнс Фортноу, Левин и Сегеди в 1991 г. (Бабай и др. 1991 г. ), Файге, Голдвассер, Лунд, Сафра и Сегеди (1991), а также Арора и Сафра в 1992 году (Арора и Сафра 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 ⊆ МИП *[бревно(п), 1,1 / 2], где MIP * [f (n), c, s] представляет собой класс сложности квантовых интерактивных систем доказательств с множеством доказательств с ж(п) -битные классические коммуникации, полнота - c, надежность - s. Они также показали, что гамильтонова версия квантовой гипотезы PCP, а именно локальная гамильтонова задача с постоянным разрывом в обещаниях c − s является QMA -жестко, следует квантовая теорема PCP игр.

Примечания

^ Инго Вегенер (2005). Теория сложности: изучение границ эффективных алгоритмов. Springer. п. 161. ISBN 978-3-540-21045-0.
^ Одед Гольдрайх (2008). Вычислительная сложность: концептуальная перспектива. Издательство Кембриджского университета. п. 405. ISBN 978-0-521-88473-0.
^ Козен, Декстер К. (2006). Теория вычислений. Тексты по информатике. Лондон: Springer-Verlag. С. 119–127. ISBN 9781846282973.
^ См. Препринт 2005 г., ECCC TR05-046. Авторитетная версия статьи Динур (2007).
^ Премия Гёделя EATSC 2019, получено 11 сентября 2019.
^ ^а ^б Ито, Цуёси; Видик, Томас (2012). «Интерактивное доказательство того, что NEXP работает против запутанных пруверов». arXiv:1207.0550 [Quant-ph ].
^ Хардести, Ларри (30.07.2012). "Пресс-релиз MIT: проблема теоретической информатики падает 10 лет назад". MIT News Office. В архиве из оригинала от 02.02.2014. Получено 2012-08-10. Интерактивные доказательства являются основой широко используемых в настоящее время криптографических систем, но для компьютерных ученых они не менее важны для понимания сложности вычислительных проблем.
^ ^а ^б Хардести, Ларри (31.07.2012). «Проблема 10-летней давности в теоретической информатике падает». MIT News Office. В архиве из оригинала от 01.08.2012. Получено 2012-08-10. Дорит Ааронов, профессор информатики и инженерии Еврейского университета в Иерусалиме, говорит, что статья Видика и Ито является квантовым аналогом более ранней статьи о многопроверочных интерактивных доказательствах, которая «в основном привела к теореме PCP, а теорема PCP не вызывает сомнений. самый важный результат за последние 20 лет ». Точно так же, по ее словам, новая статья «могла бы стать важным шагом на пути к доказательству квантового аналога теоремы PCP, которая является основным открытым вопросом в квантовой теории сложности».
^ Натараджан, А .; Видик, Т. (октябрь 2018 г.). "Низкоуровневое тестирование квантовых состояний и PCP квантовых запутанных игр для QMA". 59-й ежегодный симпозиум по основам компьютерных наук (FOCS) IEEE 2018: 731–742. arXiv:1801.03821. Bibcode:2018arXiv180103821N. Дои:10.1109 / FOCS.2018.00075. ISBN 978-1-5386-4230-6.