Изменения
→Экспандер графы
|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>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]
}}
Известно, что существуют семейства кодов <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> теоремы потребуются три операции над графами уловий:
