143
правки
Изменения
доказательство леммы
покажем, что из <tex>\mathrm{NP}</tex>-трудности задачи <tex>GAP-3SAT_s</tex> следует <tex>\mathrm{PCP}</tex> теорема.
В предположении <tex>\mathrm{NP}</tex>-трудности задачи <tex>GAP-3SAT_s</tex> любая <tex>\mathrm{NP}</tex>-полная задача, например <tex>3Color</tex> может быть сведена к <tex>GAP-3SAT_s</tex>. Таким образом мы можем свести <tex>3Color</tex> к <tex>3CNF</tex> формуле такой <tex>R(G)</tex>, что:
* <tex> G \in 3Color \Rightarrow R(G)</tex> имеет <tex>OPT=m</tex>
* <tex> G \notin 3Color \Rightarrow R(G)</tex> имеет <tex>OPT<sm</tex>
Имея такое сведение мы построим <tex>\mathcal{V}</tex> и доказательство прувера <tex>\mathcal{P}</tex> для
<tex>\mathrm {PCP}</tex> системы. <tex>\mathcal{V}</tex> запускает функцию сведения во время предподсчета,
доказателтьство <tex>\pi</tex> для данной <tex>R(G)=\psi</tex> <tex>3CNF</tex> формулы представляет собой значения пременных <tex>\psi</tex>. <tex>\mathcal{V}</tex> случайно выбирает дизъюнкт <tex>C</tex> из
<tex>\psi</tex> и проверяет, что он удовлетворяется <tex>\pi</tex>.
Понятно, что если <tex>G \in 3Color</tex>, то по определению <tex>R(G)</tex> любой дизъюнкт, выбранный
<tex>\mathcal{V}</tex> будет удовлетворен, поскольку <tex>OPT=m</tex>. Если же <tex>G \notin 3Color</tex>,
мы знаем, что <tex>OPT < sm</tex>, опять же по определению <tex>R(G)</tex>. Тaким образом вероятность того,
что <tex>\mathcal{V}</tex> выберет удовлетворенный дизъюнкт меньше <tex>s</tex>. Так как <tex>s</tex> —
константа, повторяя процесс мы можем сделать вероятность меньше <tex>\frac 1 2</tex>.
Таким образом мы показали эвивалентность <tex>\mathrm{PCP}</tex> теоремы вопросу <tex>\mathrm{NP}</tex>-трудности задачи <tex>GAP-3SAT_s</tex>.
}}
