Теорема 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 _yes , L _no ) является NP-трудной проблемой принятия решения:

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

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

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

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

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

Доказательство более слабого результата, ⁠ ${\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 году ( Бабай и др., 1991 ),Файги, Гольдвассер, Лунд, Сафра и Сегеди (1991), а также Арора и Сафра в 1992 году ( Arora & Safra 1992 ) предоставили доказательство теоремы PCP Ароры, Лунда, Мотвани, Судана и Сегеди в 1998 году ( Arora et др. 1998 ).

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

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

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

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

В 2018 году Томас Видик и Ананд Натараджан доказали ^[10] игровой вариант квантовой теоремы PCP при рандомизированной редукции. В нем говорится, что $QMA \subseteq 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]

Примечания

^ Инго Вегенер (2005). Теория сложности: исследование пределов эффективных алгоритмов . Спрингер. п. 161. ИСБН 978-3-540-21045-0 .
^ Одед Гольдрайх (2008). Вычислительная сложность: концептуальная перспектива . Издательство Кембриджского университета. п. 405. ИСБН 978-0-521-88473-0 .
^ Арора, Санджив; Барак, Вооз (2009). Вычислительная сложность: современный подход (PDF) (проект). Издательство Кембриджского университета.
^ Козен, Декстер К. (2006). Теория вычислений . Тексты по информатике. Лондон: Springer-Verlag. стр. 119–127. ISBN 9781846282973 .
^ См. препринт 2005 г., ECCC TR05-046 . Авторитетная версия статьи — Динур (2007) .
^ EATSC 2019 Gödel Prize , получено 11 сентября 2019 г.
^ Перейти обратно: ^а ^б Ито, Цуёси; Видик, Томас (2012). «Интерактивное доказательство звука NEXP с несколькими пруверами против запутанных пруверов». 53-й ежегодный симпозиум IEEE по основам компьютерных наук, FOCS 2012, Нью-Брансуик, Нью-Джерси, США, 20–23 октября 2012 г. Компьютерное общество IEEE. стр. 243–252. arXiv : 1207.0550 . дои : 10.1109/FOCS.2012.11 .
^ Хардести, Ларри (30 июля 2012 г.). «Выпуск новостей MIT: 10-летняя проблема в теоретической информатике рушится» . Пресс-служба Массачусетского технологического института. Архивировано из оригинала 2 февраля 2014 г. Проверено 10 августа 2012 г. Интерактивные доказательства являются основой широко используемых сейчас криптографических систем, но для ученых-компьютерщиков они не менее важны для понимания сложности вычислительных задач.
^ Перейти обратно: ^а ^б Хардести, Ларри (31 июля 2012 г.). «Задача 10-летней давности по теоретической информатике падает» . Пресс-служба Массачусетского технологического института. Архивировано из оригинала 1 августа 2012 г. Проверено 10 августа 2012 г. Дорит Ахаронов, профессор информатики и инженерии Еврейского университета в Иерусалиме, говорит, что статья Видика и Ито является квантовым аналогом более ранней статьи об интерактивных доказательствах с несколькими доказательствами, которые «по сути привели к теореме PCP, а теорема PCP, без сомнения, самый важный результат сложности за последние 20 лет». Точно так же, по ее словам, новая статья «может стать важным шагом на пути к доказательству квантового аналога теоремы PCP, которая является основным открытым вопросом в квантовой теории сложности».
^ Натараджан, А.; Видик, Т. (октябрь 2018 г.). «Низкостепенное тестирование квантовых состояний и PCP квантовых запутанных игр для QMA». 59-й ежегодный симпозиум IEEE по основам компьютерных наук (FOCS) , 2018 г. стр. 731–742. arXiv : 1801.03821 . Бибкод : 2018arXiv180103821N . дои : 10.1109/FOCS.2018.00075 . ISBN 978-1-5386-4230-6 . S2CID 53062680 .
^ «О гипотезе NLTS» . Саймонсский институт теории вычислений . 30 июня 2021 г. Проверено 08 августа 2022 г.
^ Аншу, Анураг; Бройкманн, Николас П.; Нирхе, Чинмей (2023). «Гамильтонианы NLTS из хороших квантовых кодов». Материалы 55-го ежегодного симпозиума ACM по теории вычислений . стр. 1090–1096. arXiv : 2206.13228 . дои : 10.1145/3564246.3585114 . ISBN 9781450399135 . S2CID 250072529 .

Ссылки

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

[Wegener2005-1] Инго Вегенер (2005). Теория сложности: исследование пределов эффективных алгоритмов . Спрингер. п. 161. ИСБН 978-3-540-21045-0 .

[Goldreich2008-2] Одед Гольдрайх (2008). Вычислительная сложность: концептуальная перспектива . Издательство Кембриджского университета. п. 405. ИСБН 978-0-521-88473-0 .

[CompComplMA-3] Арора, Санджив; Барак, Вооз (2009). Вычислительная сложность: современный подход (PDF) (проект). Издательство Кембриджского университета.

[4] Козен, Декстер К. (2006). Теория вычислений . Тексты по информатике. Лондон: Springer-Verlag. стр. 119–127. ISBN 9781846282973 .

[5] См. препринт 2005 г., ECCC TR05-046 . Авторитетная версия статьи — Динур (2007) .

[6] EATSC 2019 Gödel Prize , получено 11 сентября 2019 г.

[LANL_Vidick_Ito-7] Перейти обратно: ^а ^б Ито, Цуёси; Видик, Томас (2012). «Интерактивное доказательство звука NEXP с несколькими пруверами против запутанных пруверов». 53-й ежегодный симпозиум IEEE по основам компьютерных наук, FOCS 2012, Нью-Брансуик, Нью-Джерси, США, 20–23 октября 2012 г. Компьютерное общество IEEE. стр. 243–252. arXiv : 1207.0550 . дои : 10.1109/FOCS.2012.11 .

[eurekalert_2012-July_30-8] Хардести, Ларри (30 июля 2012 г.). «Выпуск новостей MIT: 10-летняя проблема в теоретической информатике рушится» . Пресс-служба Массачусетского технологического института. Архивировано из оригинала 2 февраля 2014 г. Проверено 10 августа 2012 г. Интерактивные доказательства являются основой широко используемых сейчас криптографических систем, но для ученых-компьютерщиков они не менее важны для понимания сложности вычислительных задач.

[MIT_newsoffice_2012_July_31-9] Перейти обратно: ^а ^б Хардести, Ларри (31 июля 2012 г.). «Задача 10-летней давности по теоретической информатике падает» . Пресс-служба Массачусетского технологического института. Архивировано из оригинала 1 августа 2012 г. Проверено 10 августа 2012 г. Дорит Ахаронов, профессор информатики и инженерии Еврейского университета в Иерусалиме, говорит, что статья Видика и Ито является квантовым аналогом более ранней статьи об интерактивных доказательствах с несколькими доказательствами, которые «по сути привели к теореме PCP, а теорема PCP, без сомнения, самый важный результат сложности за последние 20 лет». Точно так же, по ее словам, новая статья «может стать важным шагом на пути к доказательству квантового аналога теоремы PCP, которая является основным открытым вопросом в квантовой теории сложности».

[10] Натараджан, А.; Видик, Т. (октябрь 2018 г.). «Низкостепенное тестирование квантовых состояний и PCP квантовых запутанных игр для QMA». 59-й ежегодный симпозиум IEEE по основам компьютерных наук (FOCS) , 2018 г. стр. 731–742. arXiv : 1801.03821 . Бибкод : 2018arXiv180103821N . дои : 10.1109/FOCS.2018.00075 . ISBN 978-1-5386-4230-6 . S2CID 53062680 .

[11] «О гипотезе NLTS» . Саймонсский институт теории вычислений . 30 июня 2021 г. Проверено 08 августа 2022 г.

[12] Аншу, Анураг; Бройкманн, Николас П.; Нирхе, Чинмей (2023). «Гамильтонианы NLTS из хороших квантовых кодов». Материалы 55-го ежегодного симпозиума ACM по теории вычислений . стр. 1090–1096. arXiv : 2206.13228 . дои : 10.1145/3564246.3585114 . ISBN 9781450399135 . S2CID 250072529 .

[1]

[2]

[3]

[4]

[5]

[6]

[7]

[8]

[9]

[10]

[11]

[12]