143
правки
Изменения
закончено доказательство леммы в одну сторону
<tex>K</tex> дизъюнктов. <tex>\mathcal{R}</tex> возвращает конъюнкцию всех полученных формул, содержащую <tex>m=NK</tex> дизъюнктов.
Можно заметить, что из <tex>G \in 3Color</tex> по <tex>\mathrm{PCP}</tex> теореме следует, что существует <tex>\pi</tex>,
удовлетворяющее всем проверкам <tex>V</tex>. Таким образом все <tex>m</tex> дизъюнктов могут быть удовлетворены и <tex>OPT=m</tex>, что и требуется для корректности сведения <tex>\mathcal{R}</tex>.
Однако, если <tex>G \notin 3Color</tex>, хотя бы <tex>\frac N 2</tex> проверок <tex>V</tex> должны привести к отрицательному результату. Если <tex>Q_i</tex> приводит к отрицательному ответу, <tex>3CNF</tex> формула, построенная по соответствующему
предикату <tex>\phi</tex> должна быть неудовлетворимой, значит не больше <tex>K-1</tex> дизъюнктов могут быть удовлетворены.
Суммарное количество дизъюнктов, которое может быть удовлетворено:
<tex>\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</tex>
Мы показали, что из <tex>\mathrm{PCP}</tex> теоремы следует <tex>\mathrm{NP}</tex>-трудность задачи <tex>GAP-3SAT_s</tex>. Теперь
покажем, что из <tex>\mathrm{NP}</tex>-трудности задачи <tex>GAP-3SAT_s</tex> следует <tex>\mathrm{PCP}</tex> теорема.
}}
==Источники==
* [[http://eccc.hpi-web.de/report/2005/046/|The PCP Theorem by Gap Amplification, Irit Dinur, 2005]* [http://www.cs.utah.edu/~alfeld/LecturePDFs/pcp.pdf|The PCP Theorem, Notes by Scott Alfeld, 2008].
