Теорема PCP - PCP theorem
В теории сложности вычислений , то теорема PCP (также известная как теорема PCP характеризации ) утверждает , что каждая проблема решения в НП классе сложности имеет вероятностно отмечаемые доказательства ( доказательства , которые могут быть проверены с помощью рандомизированного алгоритма ) постоянной сложности запроса и логарифмической сложности случайности (использует логарифмическое количество случайных битов).
Теорема PCP гласит, что для некоторой универсальной константы K для каждого n любое математическое доказательство длины n может быть переписано как другое доказательство длины poly ( n ), которое формально проверяется с точностью 99% с помощью рандомизированного алгоритма, который проверяет только K буквы этого доказательства.
Теорема PCP является краеугольным камнем теории вычислительной сложности аппроксимации , которая исследует сложность, присущую разработке эффективных алгоритмов аппроксимации для различных задач оптимизации . Инго Вегенер назвал ее «наиболее важным результатом в теории сложности со времен теоремы Кука », а Одед Гольдрайх - «кульминацией серии впечатляющих работ […], богатых новаторскими идеями».
Официальное заявление
Теорема PCP утверждает, что
PCP и жесткость приближения
Альтернативная формулировка теоремы РСР состояний , что максимальная доля выполнимых ограничений в задаче удовлетворения ограничений является NP-трудной для аппроксимации в пределах некоторого постоянного множителя.
Формально для некоторых констант K и α <1 следующая задача обещания ( L да , L нет ) является NP-трудной проблемой решения:
- L yes = {Φ: все ограничения в Φ выполняются одновременно}
- L no = {Φ: каждое присваивание удовлетворяет менее α части ограничений Φ},
где Φ - проблема удовлетворения ограничений над булевым алфавитом с не более чем K переменных на ограничение.
Как следствие этой теоремы, можно показать, что решения многих задач естественной оптимизации, включая выполнение максимальной булевой формулы , максимальное независимое множество в графах и задачу кратчайшего вектора для решеток, не могут быть эффективно аппроксимированы, если P = NP . Эти результаты иногда также называют теоремами PCP, потому что их можно рассматривать как вероятностно проверяемые доказательства для NP с некоторой дополнительной структурой.
Доказательство
Доказательство более слабого результата NP = PCP [n 3 , 1] дано в одной из лекций Декстера Козена.
История
Теорема 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, используя графы-расширители . За это она получила премию Гёделя 2019 года .
Квантовый аналог теоремы PCP
В 2012 году Томас Видик и Цуёси Ито опубликовали результат, который показал «сильное ограничение способности запутанных испытателей вступать в сговор в многопользовательской игре». Это могло быть шагом к доказательству квантового аналога теоремы PCP, поскольку, когда результат был опубликован в СМИ, профессор Дорит Ааронов назвал его «квантовым аналогом более ранней статьи о многопроверочных интерактивных доказательствах», которая «в основном привела к PCP. Теорема ».
В 2018 году Томас Видик и Ананд Натараджан доказали игровой вариант квантовой теоремы PCP при рандомизированной редукции. В нем говорится, что QMA ⊆ MIP * [log ( n ), 1,1 / 2], где MIP * [f (n), c, s] - это класс сложности квантовых интерактивных систем доказательств с множеством доказательств с f ( n ) -битные классические коммуникации, полнота - c, надежность - s. Они также показали, что гамильтонова версия квантовой гипотезы PCP, а именно локальная гамильтонова задача с постоянным разрывом обещания c - s, является QMA- жесткой, влечет квантовую теорему PCP игр.
Заметки
Рекомендации
- Арора, Санджив ; Лунд, Карстен ; Мотвани, Раджив ; Судан, Мадху ; 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 .