PCP-теорема

Материал из Викиконспекты
Версия от 17:15, 3 июня 2012; Filchenko (обсуждение | вклад) (Несколько замечаний [TODO: переименовать]: - переименовано)
Перейти к: навигация, поиск
Теорема ([math]\mathrm{PCP}[/math] теорема):
[math]\mathrm{PCP}[log(n), O(1)] = \mathrm{NP}[/math]

Классическое доказательство [math]\mathrm{PCP}[/math] теоремы громоздкое и довольно сложное для восприятия, рассмотрим вариант докаательства, предложенный Динуром.

Лемма об эквивалентности [math]\mathrm{PCP}[/math] теоремы и [math]\mathrm{NP}[/math]-трудности [math]GAP-3SAT_s[/math]

Определение:
Задача [math]GAP-3SAT_s[/math]:
  • [math]\psi[/math][math]3CNF[/math] с [math]m[/math] дизъюнктами
  • [math]OPT[/math] — максимальное количество дизъюнктов, которые могуг быть удовлетворены одновременно
  • [math]OPT = m \Rightarrow YES[/math]
  • [math]OPT \lt sm \Rightarrow NO[/math]
  • [math]sm \lt OPT \lt m [/math] — нет ограничений на вывод


Лемма:
[math]\mathrm{PCP}[/math] теорема эквивалентна вопросу принадлежности [math]GAP-3SAT_s[/math] классу [math]\mathrm{NP}[/math]-трудных задач для некоторого [math]s[/math].
Доказательство:
[math]\triangleright[/math]

Сначала докажем, что из [math]\mathrm{PCP}[/math] теоремы следует [math]\mathrm{NP}[/math]-трудность [math]GAP-3SAT_s[/math].

Заметим, что для [math]\mathrm{NP}[/math]-полной задачи [math]3-Color[/math] существует сведение [math]\mathcal{R}[/math] к [math]GAP-3SAT_s[/math].

Из принадлежности [math]3Color[/math] [math]\mathrm{NP}[/math] и [math]\mathrm{PCP}[/math] теоремы следует, что существует доказательство [math]\pi[/math] прувера [math]\mathcal{P}[/math]. Обозначим [math]\pi_i[/math] [math]i[/math]-й бит доказательства (не его значение), будем рассматривать [math]\pi_i[/math] как переменные в [math]3SAT[/math] формуле.

По данному графу [math]G[/math], [math]\mathcal{R}[/math] нумерует все [math]N = 2^Q = 2^{O(log(n)} = poly(n)[/math] возможные случайные строки, которые может выбрать верифаер [math]V[/math]. Обозначим их [math]Q_1 ... Q_{poly(n)}[/math].

Каждая строка [math]Q_i[/math] дает нам [math]C[/math] позиций в доказательстве и предикат [math]\phi[/math]. [math]\mathcal{R}[/math] строит [math]3CNF[/math] формулу для каждого [math]\phi[/math]. Поскольку [math]\phi[/math] функция от </tex>C</tex> пременных, построенная [math]3CNF[/math] содержит не более [math]K=C2^C[/math] дизъюнктов. Для упрощения будем считать, что формула содержит [math]K[/math] дизъюнктов. [math]\mathcal{R}[/math] возвращает конъюнкцию всех полученных формул, содержащую [math]m=NK[/math] дизъюнктов.

Можно заметить, что из [math]G \in 3Color[/math] по [math]\mathrm{PCP}[/math] теореме следует, что существует [math]\pi[/math], удовлетворяющее всем проверкам [math]V[/math]. Таким образом все [math]m[/math] дизъюнктов могут быть удовлетворены и [math]OPT=m[/math], что и требуется для корректности сведения [math]\mathcal{R}[/math].

Однако, если [math]G \notin 3Color[/math], хотя бы [math]\frac N 2[/math] проверок [math]V[/math] должны привести к отрицательному результату. Если [math]Q_i[/math] приводит к отрицательному ответу, [math]3CNF[/math] формула, построенная по соответствующему предикату [math]\phi[/math] должна быть неудовлетворимой, значит не больше [math]K-1[/math] дизъюнктов могут быть удовлетворены. Суммарное количество дизъюнктов, которое может быть удовлетворено:

[math]\frac N 2 (K-1) + \frac N 2 K = \frac N 2 K(1- \frac 1 K) + \frac N 2 K = NK(1 - \frac 1 {2K}) = m(1 - \frac 1 {2k}) = sm[/math]

Мы показали, что из [math]\mathrm{PCP}[/math] теоремы следует [math]\mathrm{NP}[/math]-трудность задачи [math]GAP-3SAT_s[/math]. Теперь покажем, что из [math]\mathrm{NP}[/math]-трудности задачи [math]GAP-3SAT_s[/math] следует [math]\mathrm{PCP}[/math] теорема.

В предположении [math]\mathrm{NP}[/math]-трудности задачи [math]GAP-3SAT_s[/math] любая [math]\mathrm{NP}[/math]-полная задача, например [math]3Color[/math] может быть сведена к [math]GAP-3SAT_s[/math]. Таким образом мы можем свести [math]3Color[/math] к [math]3CNF[/math] формуле такой [math]R(G)[/math], что:

  • [math] G \in 3Color \Rightarrow R(G)[/math] имеет [math]OPT=m[/math]
  • [math] G \notin 3Color \Rightarrow R(G)[/math] имеет [math]OPT\lt sm[/math]

Имея такое сведение мы построим [math]\mathcal{V}[/math] и доказательство прувера [math]\mathcal{P}[/math] для [math]\mathrm {PCP}[/math] системы. [math]\mathcal{V}[/math] запускает функцию сведения во время предподсчета, доказателтьство [math]\pi[/math] для данной [math]R(G)=\psi[/math] [math]3CNF[/math] формулы представляет собой значения пременных [math]\psi[/math]. [math]\mathcal{V}[/math] случайно выбирает дизъюнкт [math]C[/math] из [math]\psi[/math] и проверяет, что он удовлетворяется [math]\pi[/math].

Понятно, что если [math]G \in 3Color[/math], то по определению [math]R(G)[/math] любой дизъюнкт, выбранный [math]\mathcal{V}[/math] будет удовлетворен, поскольку [math]OPT=m[/math]. Если же [math]G \notin 3Color[/math], мы знаем, что [math]OPT \lt sm[/math], опять же по определению [math]R(G)[/math]. Тaким образом вероятность того, что [math]\mathcal{V}[/math] выберет удовлетворенный дизъюнкт меньше [math]s[/math]. Так как [math]s[/math] — константа, повторяя процесс мы можем сделать вероятность меньше [math]\frac 1 2[/math].

Таким образом мы показали эвивалентность [math]\mathrm{PCP}[/math] теоремы вопросу [math]\mathrm{NP}[/math]-трудности задачи [math]GAP-3SAT_s[/math].
[math]\triangleleft[/math]

Источники