Изменения

Классическое доказательство [[Класс PCP|<tex>\mathrm{PCP}</tex>]] теоремы громоздкое и довольно сложное для восприятия,

<!--

==Лемма об эквивалентности PCP теоремы и NP-трудности GAP-3SAT==

|definition=

<tex>G=\left\langle(V,E,\Sigma,\mathcal{C}\right\rangle</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>

|about=О экспандерах

|statement=Существует <tex>d_0 \in \mathbb{N}</tex> и <tex>h_0 >0</tex> такие, что есть построимое за полиномиальное время семейство <tex>\lbrace X_n\rbrace_{n \in \mathbb{N}}</tex> <tex>d_0</tex>-регулярных графов <tex>X_n</tex> с <tex>n</tex> вершинами таких, что <tex>h(X_n) \ge h_0</tex>.

}}

{{Лемма

|statement=Пусть <tex>G</tex> <tex>d</tex>-регулярный граф со вторым по величине собственным числом <tex>\lambda</tex>. Пусть <tex>F \subseteq E</tex> множество ребер. Вероятность <tex>p</tex> того, что случайный путь, начинающийся со случайного ребра из <tex>F</tex> на <tex>i+1</tex> шаге попадет <tex>F</tex> ограничена <tex>\frac {|F|} {|E|} + \left({\frac {|\lambda|} d}\right)^i</tex>.

}}

<!--

{{Утверждение

|statement= Для любой неотрицательной случайной величины <tex>X</tex>, <tex>Pr[X>0] \ge \mathbb{E}[X^2] / \mathbb{E}[X]</tex>

}}

Известно, что существуют семейства кодов <tex>\lbrace C_n \subset \lbrace 0,1 \rbrace^n \rbrace_{n \in \mathbb{N}}</tex>, для которых уровень и расстояние равны <tex>O(n)</tex> и существует схема полиномиального размера, проверяющая <tex>x \in C_n</tex>.

!-->

==Операции на графах условий==

Для доказательства <tex>\mathrm{PCP}</tex> теоремы потребуются три операции над графами уловий:

|about=Константная степень

|statement=Любой граф условий <tex>G = \langle (V,E),\Sigma,\mathcal{C}\rangle</tex> может быть преобразован в <tex>(d_0 + 1)</tex>-регулярный граф условий <tex>G'=\langle (V',E'),\Sigma,\mathcal{C}'\rangle</tex> такой, что <tex>|V'|</tex>=2|E|</tex> и <tex>c \cdot UNSAT(G) \le UNSAT(G') \le UNSAT(G)</tex>. Для некоторых заданных констант <tex>d_0,c>0</tex>

}}

* <tex>size(G')=O(size(G))</tex>

* <tex> \frac d {d + d_0 + 1} \cdot UNSAT(G) \le UNSAT(G') \le UNSAT(G)</tex>

}}

|about=Усиление

|statement= Пусть <tex>\lambda < d</tex> и <tex>|\Sigma|</tex> произвольные константы. Тогда существует константа <tex>\beta_2=\beta_2(\lambda,d,|\Sigma|)>0</rex> такая, что для любого <tex>t \in \mathbb N</tex> и для любого <tex>d</tex>-регулярного графа условий <tex>G=\langle(V,E),\Sigma,\mathcal{C}\rangle</tex> с собственными циклами и <tex>\lambda(G)\le \lambda</tex>,<br/><tex>UNSAT(G^t) \ge \beta_2 \sqrt{t} \cdot min \left({UNSAT(G), \frac 1 t}\right)</tex>.

}}

Поскольку <tex>UNSAT(G) \le \frac 1 t</tex>, из жтой леммы следует что <tex>UNSAT(G^t) \ge O(\sqrt{t}) \cdot UNSAT(G)</tex>. Это основная техническая лемма.

===Композиция===

{{Определение