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

Материал из Викиконспекты
Перейти к: навигация, поиск
(Несколько замечаний [TODO: переименовать]: - переименовано)
(определение графов условий)
Строка 68: Строка 68:
 
Таким образом мы показали эвивалентность <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>.
 
}}
 
}}
 +
 +
==Несколько определений==
 +
{{Определение
 +
|definition= <tex>\mathcal{C}=\lbrace c_1,..., c_n\rbrace</tex> назовем множеством условий над
 +
множеством переменных <tex>V</tex>.
 +
}}
 +
{{Определение
 +
|definition=<tex>UNSAT(\mathcal{C})</tex> &mdash; минимальное подмножество неудовлетворенных условий для любых возможных назначений <tex>V</tex>.  <tex>\mathcal{C}</tex> удовлетворимо тогда и только тогда, когда <tex>UNSAT(\mathcal{C})=0</tex>. Если же <tex>\mathcal{C}</tex> неудовлетворимо, тогда <tex>UNSAT(\mathcal{C}) \ge \frac 1 n</tex>.
 +
}}
 +
 +
==Графы условий==
 +
Нам понадобятся графы ограничений для двух переменных, которые определяются следующим образом:
 +
{{Определение
 +
|definition=
 +
<tex>G=\left\langle(V,E,\Sigma,\mathcal{C}\right\rangle</tex> называется графом условий, если:
 +
* <tex>(V,E)</tex> &mdash; неориентированный граф, называемый графом, леащим в основе <tex>G</tex>.
 +
* Множество <tex>V</tex> также представляется в виде множества переменных принимающих значениями из алфавита <tex>\Sigma</tex>
 +
* Каждое ребро <tex>e \in E</tex> содержит условие <tex>c(e) \subseteq \Sigma^2</tex> и <tex>\mathcal{C}=\lbrace c(e)\rbrace_{e \in E}</tex>. Условие <tex>c(e)</tex> называется удовлетворенным парой <tex>(a, b)</tex>, если <tex>(a, b) \in c(e)</tex>
 +
}}
 +
  
 
==Источники==
 
==Источники==
 
* [http://eccc.hpi-web.de/report/2005/046/|The PCP Theorem by Gap Amplification, Irit Dinur, 2005]
 
* [http://eccc.hpi-web.de/report/2005/046/|The PCP Theorem by Gap Amplification, Irit Dinur, 2005]
 
* [http://www.cs.utah.edu/~alfeld/LecturePDFs/pcp.pdf|The PCP Theorem, Notes by Scott Alfeld, 2008]
 
* [http://www.cs.utah.edu/~alfeld/LecturePDFs/pcp.pdf|The PCP Theorem, Notes by Scott Alfeld, 2008]

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

Теорема ([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]

Несколько определений

Определение:
[math]\mathcal{C}=\lbrace c_1,..., c_n\rbrace[/math] назовем множеством условий над множеством переменных [math]V[/math].


Определение:
[math]UNSAT(\mathcal{C})[/math] — минимальное подмножество неудовлетворенных условий для любых возможных назначений [math]V[/math]. [math]\mathcal{C}[/math] удовлетворимо тогда и только тогда, когда [math]UNSAT(\mathcal{C})=0[/math]. Если же [math]\mathcal{C}[/math] неудовлетворимо, тогда [math]UNSAT(\mathcal{C}) \ge \frac 1 n[/math].


Графы условий

Нам понадобятся графы ограничений для двух переменных, которые определяются следующим образом:

Определение:
[math]G=\left\langle(V,E,\Sigma,\mathcal{C}\right\rangle[/math] называется графом условий, если:
  • [math](V,E)[/math] — неориентированный граф, называемый графом, леащим в основе [math]G[/math].
  • Множество [math]V[/math] также представляется в виде множества переменных принимающих значениями из алфавита [math]\Sigma[/math]
  • Каждое ребро [math]e \in E[/math] содержит условие [math]c(e) \subseteq \Sigma^2[/math] и [math]\mathcal{C}=\lbrace c(e)\rbrace_{e \in E}[/math]. Условие [math]c(e)[/math] называется удовлетворенным парой [math](a, b)[/math], если [math](a, b) \in c(e)[/math]


Источники