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

Материал из Викиконспекты
Перейти к: навигация, поиск
(GAP-3SAT)
 
(Начало доказательства леммы)
Строка 22: Строка 22:
 
{{Лемма
 
{{Лемма
 
|statement=<tex>\mathrm{PCP}</tex> теорема эквивалентна вопросу принадлежности
 
|statement=<tex>\mathrm{PCP}</tex> теорема эквивалентна вопросу принадлежности
<tex>GAP-3SAT_s</tex> <tex>\mathrm{NP}</tex> для некоторого <tex>s</tex>.
+
<tex>GAP-3SAT_s</tex> классу <tex>\mathrm{NP}</tex>-трудных задач для некоторого <tex>s</tex>.
 
|proof=
 
|proof=
 +
Сначала докажем, что из <tex>\mathrm{PCP}</tex> теоремы следует <tex>\mathrm{NP}</tex>-трудность <tex>GAP-3SAT_s</tex>.
 +
 +
Заметим, что для <tex>\mathrm{NP}</tex>-полной задачи <tex>3-Color</tex> существует сведение <tex>\mathcal{R}</tex> к <tex>GAP-3SAT_s</tex>.
 +
 +
Из принадлежности <tex>3Color</tex> <tex>\mathrm{NP}</tex> и <tex>\mathrm{PCP}</tex> теоремы следует, что существует
 +
доказательство <tex>\pi</tex> прувера <tex>\mathcal{P}</tex>. Обозначим <tex>\pi_i</tex> <tex>i</tex>-й бит доказательства (не его значение), будем рассматривать <tex>\pi_i</tex> как переменные в <tex>3SAT</tex> формуле.
 +
 +
По данному графу <tex>G</tex>, <tex>\mathcal{R}</tex> нумерует все <tex>N = 2^Q = 2^{O(log(n)} = poly(n)</tex> возможные
 +
случайные строки, которые может выбрать верифаер <tex>V</tex>. Обозначим их <tex>Q_1 ... Q_{poly(n)}</tex>.
 +
 +
Каждая строка <tex>Q_i</tex> дает нам <tex>C</tex> позиций в доказательстве и предикат <tex>\phi</tex>. <tex>\mathcal{R}</tex>
 +
строит <tex>3CNF</tex> формулу для каждого <tex>\phi</tex>. Поскольку <tex>\phi</tex> функция от </tex>C</tex> пременных,
 +
построенная <tex>3CNF</tex> содержит не более <tex>K=C2^C</tex> дизъюнктов. Для упрощения будем считать, что формула содержит
 +
<tex>K</tex> дизъюнктов. <tex>\mathcal{R}</tex> возвращает конъюнкцию всех полученных формул, содержащую <tex>m=NK</tex> дизъюнктов.
 +
  
 
}}
 
}}

Версия 16:01, 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]\triangleleft[/math]


Источники