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

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

Есть и критика. Так, в книге Босса говорится: «В своё время это произвело фурор. Снежный ком публикаций нарастает до сих пор … Новое, по существу, определение NP-класса проливает дополнительный свет, однако без особых последствий. … Что касается самой PCP-системы, то она существенно опирается на волшебного Оракула, и поэтому не выпускает равенство NP = PCP [O(log n ), O(1)] в практическую плоскость».

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

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

PCP и сложность аппроксимации

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

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

• L _yes = {Φ: все ограничения в Φ выполнимы}
• L _no = {Φ: при любой подстановке доля выполненных ограничений Φ не превосходит α }.

Здесь Φ — задача о выполнении ограничивающих условий над булевским алфавитом, имеющем не более K переменных на константу

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

Эти результаты иногда также называют теоремами PCP, поскольку их можно рассматривать как вероятностно проверяемые доказательства NP задач с некоторыми дополнительными структурами.

История

Теорема PCP — это кульминация долгого пути развития и вероятностно проверяемых доказательств.

Первая теорема, связывающая обычные доказательства и вероятностно проверяемые доказательства, утверждала, что ${\displaystyle NEXP\subseteq PCP[poly(n),poly(n)]}$ , и доказана в книге 1990 года .

История после первого доказательства теоремы в 1990 году

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

В 2005 году обнаружила другое доказательство теоремы PCP, используя экспандеры .

Квантовый аналог теоремы PCP

В 2012 году Томас Видик (Thomas Vidick) и Цуёси Ито (Tsuyoshi Ito) опубликовали статью , в которой показывается «сильная ограниченность возможности сложных проверок сговора в игре многих лиц». Это важный шаг вперёд к доказательству квантового аналога теоремы PCP , и профессор Дорит Ахаронов (Dorit Aharonov) назвала его «квантовым аналогом более ранней статьи об интерактивных проверках», которая, «по существу, вела к теореме PCP» .

Примечания

Литература

• Uriel Feige, Shafi Goldwasser, László Lovász, Shmuel Safra, Mario Szegedy. // Journal of the ACM. — 1996. — Т. 43 , вып. 2 . — С. 268—292 . — doi : .