143
правки
Изменения
реструктуризация
}}
==Несколько определенийОпределения и леммы, используемые в доказательстве==
{{Определение
|definition= <tex>\mathcal{C}=\lbrace c_1,..., c_n\rbrace</tex> назовем множеством условий над
}}
===Графы условий===
Нам понадобятся графы ограничений для двух переменных, которые определяются следующим образом:
{{Определение
}}
===Экспандер графы===
Экспандер графы играют важную роль во многих теоретических результатах.
}}
===Вероятности===
Следующее неравенство в стиле неравенства Чебышева удобно использовать, чтобы показать что для неотрицательной случайной величины <tex>X</tex>, <tex>Pr[X > 0] \approx \mathbb{E}[X]</tex> когда <tex>\mathbb{E}[X] \approx \mathbb{E}[X^2]</tex>.
}}
===Коды с коррекцией ошибок===
{{Определение
|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>\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> теоремы потребуются три операции над графами уловий:
* Препроцессинг. Простая операция, сохраняющая чило неудовлетворенности и размер алфавита, но делающая граф лучше.
* Усиление. Эта операция увеоичивает чило неудовлетворенности за счет увеличения размера алфавита.
* Композицияю Эта операция уменьшает размер алфавита, сохраняя число неудовлетворенности(приблизительно).
==Дополнительные материалы==
