143
правки
Изменения
expander-replacement
==Операции на графах условий==
Для доказательства <tex>\mathrm{PCP}</tex> теоремы потребуются три операции над графами уловий:
* Препроцессинг. Простая операция, сохраняющая чило неудовлетворенности (примерно) и размер алфавита, но делающая граф лучше.
* Усиление. Эта операция увеоичивает чило неудовлетворенности за счет увеличения размера алфавита.
* Композицияю Эта операция уменьшает размер алфавита, сохраняя число неудовлетворенности(приблизительно).
===Препроцессинг===
Под хорошим графом будем понимать регулярный, фиксированной степени экспандер граф.
{{Лемма
|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>. Доказательство этой леммы состоит из двух следующих лемм.
{{Лемма
|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=TODO
}}
Эта лемма известна как экспандер-замена(expander-replacement transformation).
===Усиление===
===Композиция===
==Дополнительные материалы==
* [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.
==Источники==
* [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].
