143
правки
Изменения
Начало доказательства леммы
{{Лемма
|statement=<tex>\mathrm{PCP}</tex> теорема эквивалентна вопросу принадлежности
<tex>GAP-3SAT_s</tex> классу <tex>\mathrm{NP}</tex> -трудных задач для некоторого <tex>s</tex>.
|proof=
Сначала докажем, что из <tex>\mathrm{PCP}</tex> теоремы следует <tex>\mathrm{NP}</tex>-трудность <tex>GAP-3SAT_s</tex>.
Заметим, что для <tex>\mathrm{NP}</tex>-полной задачи <tex>3-Color</tex> существует сведение <tex>\mathcal{R}</tex> к <tex>GAP-3SAT_s</tex>.
Из принадлежности <tex>3Color</tex> <tex>\mathrm{NP}</tex> и <tex>\mathrm{PCP}</tex> теоремы следует, что существует
доказательство <tex>\pi</tex> прувера <tex>\mathcal{P}</tex>. Обозначим <tex>\pi_i</tex> <tex>i</tex>-й бит доказательства (не его значение), будем рассматривать <tex>\pi_i</tex> как переменные в <tex>3SAT</tex> формуле.
По данному графу <tex>G</tex>, <tex>\mathcal{R}</tex> нумерует все <tex>N = 2^Q = 2^{O(log(n)} = poly(n)</tex> возможные
случайные строки, которые может выбрать верифаер <tex>V</tex>. Обозначим их <tex>Q_1 ... Q_{poly(n)}</tex>.
Каждая строка <tex>Q_i</tex> дает нам <tex>C</tex> позиций в доказательстве и предикат <tex>\phi</tex>. <tex>\mathcal{R}</tex>
строит <tex>3CNF</tex> формулу для каждого <tex>\phi</tex>. Поскольку <tex>\phi</tex> функция от </tex>C</tex> пременных,
построенная <tex>3CNF</tex> содержит не более <tex>K=C2^C</tex> дизъюнктов. Для упрощения будем считать, что формула содержит
<tex>K</tex> дизъюнктов. <tex>\mathcal{R}</tex> возвращает конъюнкцию всех полученных формул, содержащую <tex>m=NK</tex> дизъюнктов.
}}
