Изменения
→Графы условий
|id=pcp_th
|about=<tex>\mathrm{PCP}</tex> теорема
|statement=<tex>\mathrm{PCP}[\log(n), O(1)] = \mathrm{NP}</tex>
}}
Классическое доказательство [[Класс PCP|<tex>\mathrm{PCP}</tex>]] теоремы громоздкое и довольно сложное для восприятия,
рассмотрим вариант докаательства, предложенный ДинуромДинур. Оно основано на том, что <tex>\mathrm{PCP}</tex>-теорема [[Эквивалентность_PCP-теоремы_и_теоремы_о_трудности_аппроксимации | эквивалентна <tex>\mathrm{NP}</tex>-трудности задачи <tex>\rho-GAPqCSP</tex>]].<!--==Несколько замечаний [TODO: переименовать]Лемма об эквивалентности PCP теоремы и NP-трудности GAP-3SAT==
{{Определение
Сначала докажем, что из <tex>\mathrm{PCP}</tex> теоремы следует <tex>\mathrm{NP}</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> дизъюнктов.
Можно заметить, что из <tex>G \in 3Color</tex> по <tex>\mathrm{PCP}</tex> теореме следует, что существует <tex>\pi</tex>,
удовлетворяющее всем проверкам <tex>V</tex>. Таким образом все <tex>m</tex> дизъюнктов могут быть удовлетворены и <tex>OPT=m</tex>, что и требуется для корректности сведения <tex>\mathcal{R}</tex>.
Однако, если <tex>G \notin 3Color</tex>, хотя бы <tex>\frac N 2</tex> проверок <tex>V</tex> должны привести к отрицательному результату. Если <tex>Q_i</tex> приводит к отрицательному ответу, <tex>3CNF</tex> формула, построенная по соответствующему
предикату <tex>\phi</tex> должна быть неудовлетворимой, значит не больше <tex>K-1</tex> дизъюнктов могут быть удовлетворены.
Суммарное количество дизъюнктов, которое может быть удовлетворено:
<tex>\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</tex>
Мы показали, что из <tex>\mathrm{PCP}</tex> теоремы следует <tex>\mathrm{NP}</tex>-трудность задачи <tex>GAP-3SAT_s</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> —
константа, повторяя процесс мы можем сделать вероятность меньше <tex>\frac 1 2</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> — минимальное подмножество неудовлетворенных условий для любых возможных назначений <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> — неориентированный граф, называемый графом, лежащим в основе <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>
}}
Присваивание это отображение <tex>\sigma:V \rightarrow \Sigma</tex>, которое назначает каждой вершине из <tex>V</tex>
значение из <tex>\Sigma</tex>. Для любого присвоения <tex>\sigma</tex> определим <tex>UNSAT_\sigma(G) = \operatorname*{Pr}\limits_{(u,v)\in E} [(\sigma(u),\sigma(v)) \notin c(e)]</tex> и <tex>UNSAT(G) = \operatorname*{min}\limits_\sigma UNSAT_\sigma(G)</tex>.
Назовем <tex>UNSAT(G)</tex> числом неудовлетворенности графа <tex>G</tex>. Размером графа будем считать размер его описания <tex>size(G)=O(|V|+|E| \cdot |\Sigma|^2)</tex>
{{Лемма
|statement=Для заданного графа условий <tex>G=\left\langle(V,E,\Sigma,\mathcal{C}\right\rangle</tex>, где <tex>|\Sigma|=3</tex> проверка утверждения <tex>UNSAT(G)=0</tex> — <tex>\mathrm{NP}</tex>-трудная задача.
|proof=
Сведем <tex>3Color</tex> к нашей задаче. Дан граф <tex>G</tex>, алфавит <tex>\Sigma=\lbrace 1,2,3 \rbrace</tex> для трех цветов. Оснастим ребра условиями неравенства. Очевидно, что <tex>G \in 3Color</tex> тогда и только тогда, когда <tex>UNSAT(G)=0<tex> (Иногда удобно использовать одно и то же обозначение <tex>G</tex> для графа условий и графа, лежащего в его основе).
}}
===Экспандер графы===
Экспандер графы играют важную роль во многих теоретических результатах.
{{Определение
|definition= <tex>G=(V,E)</tex> <tex>d</tex>-регулярный граф. Положим <tex>E(S,\overline{S})=|(S \times \overline{S}) \cap E|</tex> равным количеству ребер их подмножества <tex>S\in V</tex> в его дополнение. Определим реберное расширение как
<tex>h(G)=\operatorname*{min}\limits_{S:|S|<\frac {|V|} 2} \frac {E(S, \overline S)} {|S|}</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>.
|proof=см. [http://eccc.hpi-web.de/report/2005/046 The PCP Theorem by Gap Amplification, Irit Dinur, 2005]
}}
{{Лемма
|statement= Пусть <tex>G</tex> <tex>d</tex>-регулярный граф, а <tex>h(G)</tex> его реберное расширение. Тогда <tex>\lambda(G) \le d - \frac {h(G)^2} d</tex>
}}
{{Определение
|definition=Собственным числом графа <tex>\lambda</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>.
|proof=см. [http://eccc.hpi-web.de/report/2005/046 The PCP Theorem by Gap Amplification, Irit Dinur, 2005]
}}
<!--
===Вероятности===
Следующее неравенство в стиле неравенства Чебышева удобно использовать, чтобы показать что для неотрицательной случайной величины <tex>X</tex>, <tex>Pr[X > 0] \approx \mathbb{E}[X]</tex> когда <tex>\mathbb{E}[X] \approx \mathbb{E}[X^2]</tex>.
{{Утверждение
|statement= Для любой неотрицательной случайной величины <tex>X</tex>, <tex>Pr[X>0] \ge \mathbb{E}[X^2] / \mathbb{E}[X]</tex>
|proof=см. [http://eccc.hpi-web.de/report/2005/046 The PCP Theorem by Gap Amplification, Irit Dinur, 2005]
}}
===Коды с коррекцией ошибок===
{{Определение
|definition=Кодом с коррекцией ошибок называется набор строк <tex>C \subset \Sigma^n</tex>, где <tex>\Sigma</tex> некоторый конечный алфавит. <tex>n</tex> называется размером блока, а <tex>\log_{|\Sigma|}|C|</tex> уровнем кода. Расстоянием кода называется <tex>min_{x \neq y \in C} dist(x,y)</tex>, где <tex>dist(\cdot,\cdot)</tex> — расстояние Хэмминга.
}}
Взаимнооднознаячное отображение <tex>e:D \rightarrow \Sigma^n</tex> также иногда называют кодом с коррекцией ошибок. Его уровень и расстояние определяются как уровени и расстояние его образа <tex>e(D)</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>0 < \lambda < d</tex> и <tex>\beta_1 >0</tex> такие, что любой граф условий <tex>G</tex> может быть преобразован в граф условий <tex>G'=prep(G)</tex> такой, что:
* <tex>G'</tex> <tex>d</tex>-регулярный
* <tex>G'</tex> имеет тот же алфавит, что и <tex>G</tex> и <tex>size(G') = O(size(G))</tex>.
* <tex>\beta_1 \cdot UNSAT(G) \le UNSAT(G') \le UNSAT(G)</tex>
}}
Заметим, что третий пункт теммы гарантирует поддержание полноты, т.е. если <tex>UNSAT(G)=0</tex>, то и <tex>UNSAT(G')=0</tex>. Доказательство этой леммы состоит из двух следующих лемм (<tex>\beta_1=c \cdot \frac d {d + d_0 + 1}</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>
|proof=см. [http://eccc.hpi-web.de/report/2005/046 The PCP Theorem by Gap Amplification, Irit Dinur, 2005]
}}
Эта лемма известна как экспандер-замена(expander-replacement transformation).
{{Лемма
|about=О расширении
|statement=
Пусть <tex>d_0, h_0 >0</tex> некоторые константы. Любой <tex>d</tex>-регулярный граф условий <tex>G</tex> может быть преобразован в <tex>G'</tex> такой, что:
* <tex>G'</tex> <tex>(d + d_0 + 1)</tex>-регулярный, имеет собственные циклы и <tex>\lambda(G') \le d + d_0 + 1 - \frac {h_0^2} {d + d_0 + 1} < deg(G')</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>
|proof=см. [http://eccc.hpi-web.de/report/2005/046 The PCP Theorem by Gap Amplification, Irit Dinur, 2005]
}}
===Усиление===
Это новая операция на системах условий, которая увеличивает число неудовлетворенности.
Пусть <tex>G=\langle (V,E),\Sigma,\mathcal{C}\rangle<tex> граф условий, <tex>t \in \mathbb{N}</tex>. Определим <tex>G^t=\langle (V,\mathbf{E}),\Sigma^{d^{\lceil t/2\rceil}}, \mathcal{C}^t \rangle</tex> как следующий граф условий:
* Веришины <tex>G^t</tex> совпадают с вершинами <tex>G</tex>
* Ребра: <tex>u</tex> и <tex>v</tex> соединены <tex>k</tex> ребрами в <tex>\mathbf{E}</tex>, если количество путей длины <tex>t</tex> из <tex>u</tex> в <tex>v</tex> в графе <tex>G</tex> равно <tex>k</tex>
* Алфавит: алфавит графа <tex>G^t</tex> <tex>\Sigma^{d^{\lceil t/2\rceil}}</tex>, где каждой вершине сопоставлены значения ее соседей, достижимых за <tex>\frac t 2</tex> шагов.
* Условия: Условия сопоставленные ребру <tex>e=(u,v) \in \mathbf{E}</tex> удовлетворены, если назначения для <tex>u</tex> и <tex>v</tex> согласованы с назначениями, удовлетворяющими условия, порожденные <tex>\frac t 2</tex> соседями <tex>u</tex> и <tex>v</tex>.
Если <tex>UNSAT(G)=0</tex> тогда очевидно <tex>UNSAT(G^t)=0</tex>. Интереснее доказательство того, что <tex>UNSAT(G^t) \ge O(\sqrt{t} \cdot 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>.
|proof=см. [http://eccc.hpi-web.de/report/2005/046 The PCP Theorem by Gap Amplification, Irit Dinur, 2005]
}}
Поскольку <tex>UNSAT(G) \le \frac 1 t</tex>, из жтой леммы следует что <tex>UNSAT(G^t) \ge O(\sqrt{t}) \cdot UNSAT(G)</tex>. Это основная техническая лемма.
===Композиция===
{{Определение
|about=Тестер присвоений
|definition=Тестер присвоений с алфавитом <tex>\Sigma_0</tex> и вероятностью отклонения <tex>\epsilon > 0</tex> это полиномиальное преобразование <tex>\mathcal{P}</tex>, принимающее на вход схему <tex>\Phi</tex> над будевыми переменными <tex>X</tex> и дающую на выходе граф условий <tex>G=\langle(V,E),\Sigma_0,\mathcal{C}\rangle</tex> такой, что <tex>V \subset X</tex>(в условном графе <tex>V</tex> играет одновременно две роли: переменных и вершин. <tex>Y \subset X</tex> подразумевает, что некоторые вершины из <tex>V</tex> определены с помощью переменных <tex>X</tex>). Пусть <tex>V'=V \setminus X</tex> и <tex>a : X \rightarrow \lbrace 0,1 \rbrace</tex> — присваивание.
* (Полнота) Если <tex>a \in SAT(\Phi)</tex> то существует <tex>b : V' \rightarrow \Sigma_0</tex> такое, что <tex>UNSAT_{a\cup{b}}(G)=0</tex>
* (Обоснованность) Если <tex>a \notin SAT(\Phi)</tex> то для всех <tex>b : V' \rightarrow \Sigma_0</tex>, <tex>UNSAT_{a\cup{b}}(G) \ge \epsilon \cdot dist(a, SAT(\Phi))</tex>.
}}
Следует заметить, что не накладывается никаких ограничений ни на время работы <tex>\mathcal{P}</tex> ни на <tex>size(G)</tex>. Мы игнорируем размер схемы <Tex>\Phi</tex>, которая может быть экспоненциальна относительно <tex>|X|</tex>.
{{Лемма
|about=Композиция
|statement=Пусть существует тестер присвоений <tex>\mathcal{P}</tex> с константной вероятностью отклонения <tex>\epsilon > 0</tex> и алфавитом <tex>\Sigma_0</tex>, <tex>|\Sigma_0|=O(1)</tex>. Тогда существует <tex>\beta_3 > 0</tex>, зависящая только от <tex>\mathcal{P}</tex>, такая что любой граф условий <tex>G=\langle(V,E),\Sigma,\mathcal{C}\rangle</tex> может быть преобразован в <tex>G'=\langle(V',E'),\Sigma_0,\mathcal{C}'\rangle</tex>, обозначаемый <tex>G \circ \mathcal{C}</tex>, такой что <tex>size(G')=M(|\Sigma|) \cdot size(G)</tex> и <tex>\beta_3 \cdot UNSAT(G) \le UNSAT(G') \le UNSAT(G)</tex>
|proof=см. [http://eccc.hpi-web.de/report/2005/046 The PCP Theorem by Gap Amplification, Irit Dinur, 2005]
}}
==Основная теорема==
Основываясь на операциях с графами условий мы можем доказать основную теорему.
{{Теорема
|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=Сведем удовлетворимость графа условий к нашей задаче. Пусть <tex>G</tex> задача удовлетворимости некоторого графа с <tex>|\Sigma|=3</tex>. Идей состоит в повторении применения основной теоремы до тех пор, пока число неудовлетворенности не станет постоянным.
Пусть <tex>G_0 = G</tex> и <tex>G_i(i \ge 1)</tex> — результат применения основной теоремы к <tex>G_{i-1}</tex>. Тогда для <tex>i \ge 1</tex> <tex>G</tex> — граф условий с алфавитом <tex>\Sigma_0</tex>. Пусть <tex>E_0</tex> — множество ребер <tex>G_0<tex> и <tex>k=\log|E_0|=O(\log n)</tex>.
Полнота показывается тривиально: если <tex>UNSAT(G_0)=0</tex>, то для всех <tex>i</tex> <tex>UNSAT(G_i)=0</tex>. Для обоснованности рассмотрим <tex>UNSAT(G_0) > 0</tex>. Если для некоторого <tex>i*<k</tex>, <tex>UNSAT(G_{i*}) \ge \frac \alpha 2</tex>, то из основной теоремы следует, что для всех <tex>i>i*</tex> <tex>UNSAT(G_i)\ge \alpha</tex>. На остальные <tex>i</tex> это распространяется по индукции <tex>UNSAT(G_i) \ge min(2^i UNSAT(G_0), \alpha)</tex>.
Если <tex>UNSAT(G_0)>0</tex>, то <tex>UNSAT(G_0)\ge \frac 1 {|E_0|}</tex>. Конечно, <tex>2^k UNSAT(G_0) > \alpha</tex>. Таким образом <tex>UNSAT(G_k) \ge \alpha</tex>.
Такми образом <tex>\rho -GAP2CSP</tex> <tex>\mathrm{NP}</tex>-трудная. Достичь обоснованности <tex>\frac 1 2</tex> можно последовательным повторением <tex>u=\frac 1 {\log(\frac 1 {1 - \alpha})} </tex> раз. Тоесть создать новые условия, представляющие собой <tex>AND</tex> всех возможных <tex>u</tex>-наборов прежних условий. Конечно, при этом количество запросов на условие увеличится до <tex>2u</tex>.
}}
==Дополнительные материалы==
* [http://www.math.ias.edu/boaz/ExpanderCourse/|N. Linial and A. Wigderson. Expander graphs and their applications. Lecture notes of a course, 2003].
* Michael Sipser and Daniel A. Spielman. Expander codes. IEEE Trans. Inform. Theory, 42(6, part 1):1710–1722, 1996. Codes and complexity.
* C. Papadimitriou and M. Yannakakis. Optimization, approximation and complexity classes. Journal of Computer and System Sciences, 3:425–440, 1991.
* Irit Dinur and Omer Reingold. Assignment testers: Towards combinatorial proofs of the PCP theorem. In Proceedings of the 45th Symposium on Foundations of Computer Science (FOCS), 2004.
==Источники==
* [[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].
