143
правки
Изменения
основная теорема
рассмотрим вариант докаательства, предложенный Динуром.
==Лемма об эквивалентности <tex>\mathrm{PCP}</tex> теоремы и <tex>\mathrm{NP}</tex>-трудности <tex>GAP-3SAT_s</tex>3SAT==
{{Определение
}}
==Основная теорема==
Основываясь на операциях с графами условий мы можем доказать основную теорему.
{{Теорема
|about=Основная теорема
|statement=Для любого <tex>\Sigma</tex>, <tex>|\Sigma|=O(1)</tex> существуют константы <tex>C > 0</tex> и <tex>0 < \alpha < 1</tex> такие, что для данного графа условий <tex>G=\langle(V,E),\Sigma,\mathcal{C}\rangle</tex> за полиномиальное время можно построить граф условий <tex>G'=\langle(V',E'),\Sigma_0,\mathcal{C}'\rangle</tex> такой, что:
* <tex>size(G') \le C \cdot size(G)</tex> и <tex>|\Sigma_0| = O(1)</tex>
* (Полнота) Если <tex>UNSAT(G)=0</tex>, то <tex>UNSAT(G')=0</tex>
* (Обоснованность) <tex>UNSAT(G') \ge min(2 \cdot UNSAT(G), \alpha)</tex>
|proof=
Построим <tex>G'</tex> по <tex>G</tex> следующим образом: <tex>G'=(prep(G))^t \circ \mathcal{P}</tex>.
# (Препроцессинг) Пусть <tex>H_1=prep(G)</tex>. Существуют некоторые глобальные константы <tex>\lambda < d </tex> и <tex>\beta_1 >0</tex> такие, что <tex>H_1</tex> <tex>d</tex>-регулярный, имеет тот же алфавит, что и <tex>G</tex>, <tex>\lambda(H_1) \le \lambda < d</tex> и <tex>\beta_1 \cdot UNSAT*G( \le UNSAT(H_1) \le UNSAT(G)</tex>.
# (Усиление) Пусть <tex>H_2=(H_1)^t</tex> для достаточно большой константы <tex> t > 1</tex>, которую определим ниже. Существует некоторая константа <tex>\beta_2=\beta(\lambda, d, |\Sigma|) > 0</tex>, для которой <tex>UNSAT(H_2) \ge \beta_2 \sqrt{t} \cdot min(UNSAT(H_1), \frac 1 t)</tex>. Однако, алфавит вырос до <tex>\Sigma^{d^{\lceil t / 2 \rceil}}</tex>.
# (Композиция) Пусть <tex>G'=H_2 \circ \mathcal{P}</tex>. Это уменьшит алфавит до <tex>\Sigma_0</tex>, при <tex>\beta_3 \cdot UNSAT(H_2) \le UNSAT(G') \le UNSAT(H_2)</tex> для некоторой <tex>\beta_3 > 0 </tex>.
Проверим выполнение условий теоремы. Размер <tex>G'</tex> линеен относительно размера<tex>G</tex>, поскольку на каждом шагу увеличивался линейно. Полнота явно поддерживается на каждом шаге. Теперь выберем <tex>t=\left\lceil\left({\frac 2 {\beta_1\beta_2\beta_3}}\right)^2\right\rceil</tex>. Пусть <tex>\alpha=\frac {\beta_3\beta_2} {sqrt{t}}</tex>.
Таким образом,
<tex>UNSAT(G') \ge \beta_3 \cdot UNSAT(H_2)</tex><br/><tex>\ge \beta_3 \cdot \beta_2 \sqrt{t} \cdot min(UNSAT(H_1), \frac 1 t)</tex><br/><tex>\ge \beta_3 \cdot \beta_2 \sqrt{t} \cdot min(\beta_1 UNSAT(G_, \frac 1 t) </tex><br/><tex>\ge min(2 \cdot UNSAT(G), \alpha)</tex>
}}
===Доказательство PCP теоремы===
{{Лемма
|statement=Следствием из основной теоремы является <tex>\mathrm{NP}</tex>-трудность <tex>GAP-3SAT_s</tex>.
|proof=
}}
==Дополнительные материалы==
* [http://www.math.ias.edu/boaz/ExpanderCourse/|N. Linial and A. Wigderson. Expander graphs and their applications. Lecture notes of a course, 2003].
