Материал из Викиконспекты
| Теорема ([math]\mathrm{PCP}[/math] теорема): |
[math]\mathrm{PCP}[log(n), O(1)] = \mathrm{NP}[/math] |
Классическое доказательство [math]\mathrm{PCP}[/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]\triangleleft[/math] |
Источники
