PCP-теорема — различия между версиями

Материал из Викиконспекты
Перейти к: навигация, поиск
(закончено доказательство леммы в одну сторону)
(доказательство леммы)
Строка 51: Строка 51:
 
покажем, что из <tex>\mathrm{NP}</tex>-трудности задачи <tex>GAP-3SAT_s</tex> следует <tex>\mathrm{PCP}</tex> теорема.
 
покажем, что из <tex>\mathrm{NP}</tex>-трудности задачи <tex>GAP-3SAT_s</tex> следует <tex>\mathrm{PCP}</tex> теорема.
  
 +
В предположении <tex>\mathrm{NP}</tex>-трудности задачи <tex>GAP-3SAT_s</tex> любая <tex>\mathrm{NP}</tex>-полная задача, например <tex>3Color</tex> может быть сведена к <tex>GAP-3SAT_s</tex>. Таким образом мы можем свести <tex>3Color</tex> к <tex>3CNF</tex> формуле такой <tex>R(G)</tex>, что:
 +
* <tex> G \in 3Color \Rightarrow R(G)</tex> имеет <tex>OPT=m</tex>
 +
* <tex> G \notin 3Color \Rightarrow R(G)</tex> имеет <tex>OPT<sm</tex>
 +
 +
Имея такое сведение мы построим <tex>\mathcal{V}</tex> и доказательство прувера <tex>\mathcal{P}</tex> для
 +
<tex>\mathrm {PCP}</tex> системы. <tex>\mathcal{V}</tex> запускает функцию сведения во время предподсчета,
 +
доказателтьство <tex>\pi</tex> для данной <tex>R(G)=\psi</tex> <tex>3CNF</tex> формулы представляет собой значения пременных <tex>\psi</tex>. <tex>\mathcal{V}</tex> случайно выбирает дизъюнкт <tex>C</tex> из
 +
<tex>\psi</tex> и проверяет, что он удовлетворяется <tex>\pi</tex>.
 +
 +
Понятно, что если <tex>G \in 3Color</tex>, то по определению <tex>R(G)</tex> любой дизъюнкт, выбранный
 +
<tex>\mathcal{V}</tex> будет удовлетворен, поскольку <tex>OPT=m</tex>. Если же <tex>G \notin 3Color</tex>,
 +
мы знаем, что <tex>OPT < sm</tex>, опять же по определению <tex>R(G)</tex>. Тaким образом вероятность того,
 +
что <tex>\mathcal{V}</tex> выберет удовлетворенный дизъюнкт меньше <tex>s</tex>. Так как <tex>s</tex> &mdash;
 +
константа, повторяя процесс мы можем сделать вероятность меньше <tex>\frac 1 2</tex>.
 +
 +
Таким образом мы показали эвивалентность <tex>\mathrm{PCP}</tex> теоремы вопросу <tex>\mathrm{NP}</tex>-трудности задачи <tex>GAP-3SAT_s</tex>.
 
}}
 
}}
  

Версия 17:11, 3 июня 2012

Теорема ([math]\mathrm{PCP}[/math] теорема):
[math]\mathrm{PCP}[log(n), O(1)] = \mathrm{NP}[/math]

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

Несколько замечаний [TODO: переименовать]

Определение:
Задача [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]


Источники