Теорема PCP - PCP theorem

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

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

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

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

Теорема 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] дано в одной из лекций Декстера Козена.

История

Теорема 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 игр.

Заметки

Рекомендации