| Теорема ([math]\mathrm{PCP}[/math] теорема): |
[math]\mathrm{PCP}[log(n), O(1)] = \mathrm{NP}[/math] |
Классическое доказательство [math]\mathrm{PCP}[/math] теоремы громоздкое и довольно сложное для восприятия,
рассмотрим вариант докаательства, предложенный Динуром.
Лемма об эквивалентности [math]\mathrm{PCP}[/math] теоремы и [math]\mathrm{NP}[/math]-трудности [math]GAP-3SAT_s[/math]
| Определение: |
Задача [math]GAP-3SAT_s[/math]:
- [math]\psi[/math] — [math]3CNF[/math] с [math]m[/math] дизъюнктами
- [math]OPT[/math] — максимальное количество дизъюнктов, которые могуг быть удовлетворены одновременно
- [math]OPT = m \Rightarrow YES[/math]
- [math]OPT \lt sm \Rightarrow NO[/math]
- [math]sm \lt OPT \lt m [/math] — нет ограничений на вывод
|
| Лемма: |
[math]\mathrm{PCP}[/math] теорема эквивалентна вопросу принадлежности
[math]GAP-3SAT_s[/math] классу [math]\mathrm{NP}[/math]-трудных задач для некоторого [math]s[/math]. |
| Доказательство: |
| [math]\triangleright[/math] |
|
Сначала докажем, что из [math]\mathrm{PCP}[/math] теоремы следует [math]\mathrm{NP}[/math]-трудность [math]GAP-3SAT_s[/math].
Заметим, что для [math]\mathrm{NP}[/math]-полной задачи [math]3-Color[/math] существует сведение [math]\mathcal{R}[/math] к [math]GAP-3SAT_s[/math].
Из принадлежности [math]3Color[/math] [math]\mathrm{NP}[/math] и [math]\mathrm{PCP}[/math] теоремы следует, что существует
доказательство [math]\pi[/math] прувера [math]\mathcal{P}[/math]. Обозначим [math]\pi_i[/math] [math]i[/math]-й бит доказательства (не его значение), будем рассматривать [math]\pi_i[/math] как переменные в [math]3SAT[/math] формуле.
По данному графу [math]G[/math], [math]\mathcal{R}[/math] нумерует все [math]N = 2^Q = 2^{O(log(n)} = poly(n)[/math] возможные
случайные строки, которые может выбрать верифаер [math]V[/math]. Обозначим их [math]Q_1 ... Q_{poly(n)}[/math].
Каждая строка [math]Q_i[/math] дает нам [math]C[/math] позиций в доказательстве и предикат [math]\phi[/math]. [math]\mathcal{R}[/math]
строит [math]3CNF[/math] формулу для каждого [math]\phi[/math]. Поскольку [math]\phi[/math] функция от </tex>C</tex> пременных,
построенная [math]3CNF[/math] содержит не более [math]K=C2^C[/math] дизъюнктов. Для упрощения будем считать, что формула содержит
[math]K[/math] дизъюнктов. [math]\mathcal{R}[/math] возвращает конъюнкцию всех полученных формул, содержащую [math]m=NK[/math] дизъюнктов.
Можно заметить, что из [math]G \in 3Color[/math] по [math]\mathrm{PCP}[/math] теореме следует, что существует [math]\pi[/math],
удовлетворяющее всем проверкам [math]V[/math]. Таким образом все [math]m[/math] дизъюнктов могут быть удовлетворены и [math]OPT=m[/math], что и требуется для корректности сведения [math]\mathcal{R}[/math].
Однако, если [math]G \notin 3Color[/math], хотя бы [math]\frac N 2[/math] проверок [math]V[/math] должны привести к отрицательному результату. Если [math]Q_i[/math] приводит к отрицательному ответу, [math]3CNF[/math] формула, построенная по соответствующему
предикату [math]\phi[/math] должна быть неудовлетворимой, значит не больше [math]K-1[/math] дизъюнктов могут быть удовлетворены.
Суммарное количество дизъюнктов, которое может быть удовлетворено:
[math]\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[/math]
Мы показали, что из [math]\mathrm{PCP}[/math] теоремы следует [math]\mathrm{NP}[/math]-трудность задачи [math]GAP-3SAT_s[/math]. Теперь
покажем, что из [math]\mathrm{NP}[/math]-трудности задачи [math]GAP-3SAT_s[/math] следует [math]\mathrm{PCP}[/math] теорема.
В предположении [math]\mathrm{NP}[/math]-трудности задачи [math]GAP-3SAT_s[/math] любая [math]\mathrm{NP}[/math]-полная задача, например [math]3Color[/math] может быть сведена к [math]GAP-3SAT_s[/math]. Таким образом мы можем свести [math]3Color[/math] к [math]3CNF[/math] формуле такой [math]R(G)[/math], что:
- [math] G \in 3Color \Rightarrow R(G)[/math] имеет [math]OPT=m[/math]
- [math] G \notin 3Color \Rightarrow R(G)[/math] имеет [math]OPT\lt sm[/math]
Имея такое сведение мы построим [math]\mathcal{V}[/math] и доказательство прувера [math]\mathcal{P}[/math] для
[math]\mathrm {PCP}[/math] системы. [math]\mathcal{V}[/math] запускает функцию сведения во время предподсчета,
доказателтьство [math]\pi[/math] для данной [math]R(G)=\psi[/math] [math]3CNF[/math] формулы представляет собой значения пременных [math]\psi[/math]. [math]\mathcal{V}[/math] случайно выбирает дизъюнкт [math]C[/math] из
[math]\psi[/math] и проверяет, что он удовлетворяется [math]\pi[/math].
Понятно, что если [math]G \in 3Color[/math], то по определению [math]R(G)[/math] любой дизъюнкт, выбранный
[math]\mathcal{V}[/math] будет удовлетворен, поскольку [math]OPT=m[/math]. Если же [math]G \notin 3Color[/math],
мы знаем, что [math]OPT \lt sm[/math], опять же по определению [math]R(G)[/math]. Тaким образом вероятность того,
что [math]\mathcal{V}[/math] выберет удовлетворенный дизъюнкт меньше [math]s[/math]. Так как [math]s[/math] —
константа, повторяя процесс мы можем сделать вероятность меньше [math]\frac 1 2[/math].
Таким образом мы показали эвивалентность [math]\mathrm{PCP}[/math] теоремы вопросу [math]\mathrm{NP}[/math]-трудности задачи [math]GAP-3SAT_s[/math]. |
| [math]\triangleleft[/math] |
Определения и леммы, используемые в доказательстве
| Определение: |
| [math]\mathcal{C}=\lbrace c_1,..., c_n\rbrace[/math] назовем множеством условий над
множеством переменных [math]V[/math]. |
| Определение: |
| Число неудовлетворенности [math]UNSAT(\mathcal{C})[/math] — минимальное подмножество неудовлетворенных условий для любых возможных назначений [math]V[/math]. [math]\mathcal{C}[/math] удовлетворимо тогда и только тогда, когда [math]UNSAT(\mathcal{C})=0[/math]. Если же [math]\mathcal{C}[/math] неудовлетворимо, тогда [math]UNSAT(\mathcal{C}) \ge \frac 1 n[/math]. |
Графы условий
Нам понадобятся графы ограничений для двух переменных, которые определяются следующим образом:
| Определение: |
[math]G=\left\langle(V,E,\Sigma,\mathcal{C}\right\rangle[/math] называется графом условий, если:
- [math](V,E)[/math] — неориентированный граф, называемый графом, леащим в основе [math]G[/math].
- Множество [math]V[/math] также представляется в виде множества переменных принимающих значениями из алфавита [math]\Sigma[/math]
- Каждое ребро [math]e \in E[/math] содержит условие [math]c(e) \subseteq \Sigma^2[/math] и [math]\mathcal{C}=\lbrace c(e)\rbrace_{e \in E}[/math]. Условие [math]c(e)[/math] называется удовлетворенным парой [math](a, b)[/math], если [math](a, b) \in c(e)[/math]
|
Присваивание это отображение [math]\sigma:V \rightarrow \Sigma[/math], которое назначает каждой вершине из [math]V[/math]
значение из [math]\Sigma[/math]. Для любого присвоения [math]\sigma[/math] определим [math]UNSAT_\sigma(G) = \operatorname*{Pr}\limits_{(u,v)\in E} [(\sigma(u),\sigma(v)) \notin c(e)][/math] и [math]UNSAT(G) = \operatorname*{min}\limits_\sigma UNSAT_\sigma(G)[/math].
Назовем [math]UNSAT(G)[/math] числом неудовлетворенности графа [math]G[/math]. Размером графа будем считать размер его описания [math]size(G)=O(|V|+|E| \cdot |\Sigma|^2)[/math]
| Лемма: |
Для заданного графа условий [math]G=\left\langle(V,E,\Sigma,\mathcal{C}\right\rangle[/math], где [math]|\Sigma|=3[/math] проверка утверждения [math]UNSAT(G)=0[/math] — [math]\mathrm{NP}[/math]-трудная задача. |
| Доказательство: |
| [math]\triangleright[/math] |
|
Сведем [math]3Color[/math] к нашей задаче. Дан граф [math]G[/math], алфавит [math]\Sigma=\lbrace 1,2,3 \rbrace[/math] для трех цветов. Оснастим ребра условиями неравенства. Очевидно, что [math]G \in 3Color[/math] тогда и только тогда, когда [math]UNSAT(G)=0\lt tex\gt (Иногда удобно использовать одно и то же обозначение \lt tex\gt G[/math] для графа условий и графа, лежащего в его основе). |
| [math]\triangleleft[/math] |
Экспандер графы
Экспандер графы играют важную роль во многих теоретических результатах.
| Определение: |
| [math]G=(V,E)[/math] [math]d[/math]-регулярный граф. Положим [math]E(S,\overline{S})=|(S \times \overline{S}) \cap E|[/math] равным количеству ребер их подмножества [math]S\in V[/math] в его дополнение. Определим реберное расширение как
[math]h(G)=\operatorname*{min}\limits_{S:|S|\lt \frac {|V|} 2} \frac {E(S, \overline S)} {|S|}[/math] |
| Лемма (О экспандерах): |
Существует [math]d_0 \in \mathbb{N}[/math] и [math]h_0 \gt 0[/math] такие, что есть построимое за полиномиальное время семейство [math]\lbrace X_n\rbrace_{n \in \mathbb{N}}[/math] [math]d_0[/math]-регулярных графов [math]X_n[/math] с [math]n[/math] вершинами таких, что [math]h(X_n) \ge h_0[/math]. |
| Доказательство: |
| [math]\triangleright[/math] |
|
TODO |
| [math]\triangleleft[/math] |
| Лемма: |
Пусть [math]G[/math] [math]d[/math]-регулярный граф, а [math]h(G)[/math] его реберное расширение. Тогда [math]\lambda(G) \le d - \frac {h(G)^2} d[/math] |
| Определение: |
| Собственным числом графа [math]\lambda[/math] называют собственное число его матрицы смежности. |
| Лемма: |
Пусть [math]G[/math] [math]d[/math]-регулярный граф со вторым по величине собственным числом [math]\lambda[/math]. Пусть [math]F \subseteq E[/math] множество ребер. Вероятность [math]p[/math] того, что случайный путь, начинающийся со случайного ребра из [math]F[/math] на [math]i+1[/math] шаге попадет [math]F[/math] ограничена [math]\frac {|F|} {|E|} + \left({\frac {|\lambda|} d}\right)^i[/math]. |
| Доказательство: |
| [math]\triangleright[/math] |
|
TODO |
| [math]\triangleleft[/math] |
Вероятности
Следующее неравенство в стиле неравенства Чебышева удобно использовать, чтобы показать что для неотрицательной случайной величины [math]X[/math], [math]Pr[X \gt 0] \approx \mathbb{E}[X][/math] когда [math]\mathbb{E}[X] \approx \mathbb{E}[X^2][/math].
| Утверждение: |
Для любой неотрицательной случайной величины [math]X[/math], [math]Pr[X\gt 0] \ge \mathbb{E}[X^2] / \mathbb{E}[X][/math] |
| [math]\triangleright[/math] |
|
TODO |
| [math]\triangleleft[/math] |
Коды с коррекцией ошибок
| Определение: |
| Кодом с коррекцией ошибок называется набор строк [math]C \subset \Sigma^n[/math], где [math]\Sigma[/math] некоторый конечный алфавит. [math]n[/math] называется размером блока, а [math]log_{|\Sigma|}|C|[/math] уровнем кода. Расстоянием кода называется [math]min_{x \neq y \in C} dist(x,y)[/math], где [math]dist(\cdot,\cdot)[/math] — расстояние Хэмминга. |
Взаимнооднознаячное отображение [math]e:D \rightarrow \Sigma^n[/math] также иногда называют кодом с коррекцией ошибок. Его уровень и расстояние определяются как уровени и расстояние его образа [math]e(D)[/math].
Известно, что существуют семейства кодов [math]\lbrace C_n \subset \lbrace 0,1 \rbrace^n \rbrace_{n \in \mathbb{N}}[/math], для которых уровень и расстояние равны [math]O(n)[/math] и существует схема полиномиального размера, проверяющая [math]x \in C_n[/math].
Операции на графах условий
Для доказательства [math]\mathrm{PCP}[/math] теоремы потребуются три операции над графами уловий:
- Препроцессинг. Простая операция, сохраняющая чило неудовлетворенности(примерно) и размер алфавита, но делающая граф лучше.
- Усиление. Эта операция увеоичивает чило неудовлетворенности за счет увеличения размера алфавита.
- Композицияю Эта операция уменьшает размер алфавита, сохраняя число неудовлетворенности(приблизительно).
Препроцессинг
Под хорошим графом будем понимать регулярный, фиксированной степени экспандер граф.
| Лемма (Препроцессинг): |
существуют константы [math]0 \lt \lambda \lt d[/math] и [math]\beta_1 \gt 0[/math] такие, что любой граф условий [math]G[/math] может быть преобразован в граф условий [math]G'=prep(G)[/math] такой, что:
- [math]G'[/math] [math]d[/math]-регулярный
- [math]G'[/math] имеет тот же алфавит, что и [math]G[/math] и [math]size(G') = O(size(G))[/math].
- [math]\beta_1 \cdot UNSAT(G) \le UNSAT(G') \le UNSAT(G)[/math]
|
Заметим, что третий пункт теммы гарантирует поддержание полноты, т.е. если [math]UNSAT(G)=0[/math], то и [math]UNSAT(G')=0[/math]. Доказательство этой леммы состоит из двух следующих лемм ([math]\beta_1=c \cdot \frac d {d + d_0 + 1}[/math]).
| Лемма (Константная степень): |
Любой граф условий [math]G = \langle (V,E),\Sigma,\mathcal{C}\rangle[/math] может быть преобразован в [math](d_0 + 1)[/math]-регулярный граф условий [math]G'=\langle (V',E'),\Sigma,\mathcal{C}'\rangle[/math] такой, что [math]|V'|[/math]=2 |
| Доказательство: |
| [math]\triangleright[/math] |
|
TODO |
| [math]\triangleleft[/math] |
Эта лемма известна как экспандер-замена(expander-replacement transformation).
| Лемма (О расширении): |
Пусть [math]d_0, h_0 \gt 0[/math] некоторые константы. Любой [math]d[/math]-регулярный граф условий [math]G[/math] может быть преобразован в [math]G'[/math] такой, что:
- [math]G'[/math] [math](d + d_0 + 1)[/math]-регулярный, имеет собственные циклы и [math]\lambda(G') \le d + d_0 + 1 - \frac {h_0^2} {d + d_0 + 1} \lt deg(G')[/math]
- [math]size(G')=O(size(G))[/math]
- [math] \frac d {d + d_0 + 1} \cdot UNSAT(G) \le UNSAT(G') \le UNSAT(G)[/math]
|
| Доказательство: |
| [math]\triangleright[/math] |
|
TODO |
| [math]\triangleleft[/math] |
Усиление
Это новая операция на системах условий, которая увеличивает число неудовлетворенности.
Пусть [math]G=\langle (V,E),\Sigma,\mathcal{C}\rangle\lt tex\gt граф условий, \lt tex\gt t \in \mathbb{N}[/math]. Определим [math]G^t=\langle (V,\mathbf{E}),\Sigma^{d^{\lceil t/2\rceil}}, \mathcal{C}^t \rangle[/math] как следующий граф условий:
- Веришины [math]G^t[/math] совпадают с вершинами [math]G[/math]
- Ребра: [math]u[/math] и [math]v[/math] соединены [math]k[/math] ребрами в [math]\mathbf{E}[/math], если количество путей длины [math]t[/math] из [math]u[/math] в [math]v[/math] в графе [math]G[/math] равно [math]k[/math]
- Алфавит: алфавит графа [math]G^t[/math] [math]\Sigma^{d^{\lceil t/2\rceil}}[/math], где каждой вершине сопоставлены значения ее соседей, достижимых за [math]\frac t 2[/math] шагов.
- Условия: Условия сопоставленные ребру [math]e=(u,v) \in \mathbf{E}[/math] удовлетворены, если назначения для [math]u[/math] и [math]v[/math] согласованы с назначениями, удовлетворяющими условия, порожденные [math]\frac t 2[/math] соседями [math]u[/math] и [math]v[/math].
Если [math]UNSAT(G)=0[/math] тогда очевидно [math]UNSAT(G^t)=0[/math]. Интереснее доказательство того, что [math]UNSAT(G^t) \ge O(\sqrt{t} \cdot UNSAT(G)[/math].
| Лемма (Усиление): |
Пусть [math]\lambda \lt d[/math] и [math]|\Sigma|[/math] произвольные константы. Тогда существует константа [math]\beta_2=\beta_2(\lambda,d,|\Sigma|)\gt 0\lt /rex\gt такая, что для любого \lt tex\gt t \in \mathbb N[/math] и для любого [math]d[/math]-регулярного графа условий [math]G=\langle(V,E),\Sigma,\mathcal{C}\rangle[/math] с собственными циклами и [math]\lambda(G)\le \lambda[/math],
[math]UNSAT(G^t) \ge \beta_2 \sqrt{t} \cdot min \left({UNSAT(G), \frac 1 t}\right)[/math]. |
| Доказательство: |
| [math]\triangleright[/math] |
|
TODO |
| [math]\triangleleft[/math] |
Поскольку [math]UNSAT(G) \le \frac 1 t[/math], из жтой леммы следует что [math]UNSAT(G^t) \ge O(\sqrt{t}) \cdot UNSAT(G)[/math]. Это основная техническая лемма.
Композиция
| Определение: |
Тестер присвоений с алфавитом [math]\Sigma_0[/math] и вероятностью отклонения [math]\epsilon \gt 0[/math] это полиномиальное преобразование [math]\mathcal{P}[/math], принимающее на вход схему [math]\Phi[/math] над будевыми переменными [math]X[/math] и дающую на выходе граф условий [math]G=\langle(V,E),\Sigma_0,\mathcal{C}\rangle[/math] такой, что [math]V \subset X[/math](в условном графе [math]V[/math] играет одновременно две роли: переменных и вершин. [math]Y \subset X[/math] подразумевает, что некоторые вершины из [math]V[/math] определены с помощью переменных [math]X[/math]). Пусть [math]V'=V \setminus X[/math] и [math]a : X \rightarrow \lbrace 0,1 \rbrace[/math] — присваивание.
- (Полнота) Если [math]a \in SAT(\Phi)[/math] то существует [math]b : V' \rightarrow \Sigma_0[/math] такое, что [math]UNSAT_{a\cup{b}}(G)=0[/math]
- (Обоснованность) Если [math]a \notin SAT(\Phi)[/math] то для всех [math]b : V' \rightarrow \Sigma_0[/math], [math]UNSAT_{a\cup{b}}(G) \ge \epsilon \cdot dist(a, SAT(\Phi))[/math].
|
Следует заметить, что не накладывается никаких ограничений ни на время работы [math]\mathcal{P}[/math] ни на [math]size(G)[/math]. Мы игнорируем размер схемы [math]\Phi[/math], которая может быть экспоненциальна относительно [math]|X|[/math].
Дополнительные материалы
- 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.
Источники
