143
правки
Изменения
Вступление композиции
Поскольку <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>.
==Дополнительные материалы==
* [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].
