143
правки
Изменения
доказательство PCP
{{Лемма
|statement=Следствием из основной теоремы является <tex>\mathrm{NP}</tex>-трудность <tex>GAP-3SAT_s</tex>.
|proof=Сведем удовлетворимость графа условий к нашей задаче. Пусть <tex>G</tex> задача удовлетворимости некоторого графа с <tex>|\Sigma|=3</tex>. Идей состоит в повторении применения основной теоремы до тех пор, пока число неудовлетворенности не станет постоянным. Пусть <tex>G_0 = G</tex> и <tex>G_i(i \ge 1)</tex> — результат применения основной теоремы к <tex>G_{i-1}</tex>. Тогда для <tex>i \ge 1</tex> <tex>G</tex> — граф условий с алфавитом <tex>\Sigma_0</tex>. Пусть <tex>E_0</tex> — множество ребер <tex>G_0<tex> и <tex>k=log|E_0|=O(log n)</tex>. Полнота показывается тривиально: если <tex>UNSAT(G_0)=0</tex>, то для всех <tex>i</tex> <tex>UNSAT(G_i)=0</tex>. Для обоснованности рассмотрим <tex>UNSAT(G_0) > 0</tex>. Если для некоторого <tex>i*<k</tex>, <tex>UNSAT(G_{i*}) \ge \frac \alpha 2</tex>, то из основной теоремы следует, что для всех <tex>i>i*</tex> <tex>UNSAT(G_i)\ge \alpha</tex>. На остальные <tex>i</tex> это распространяется по индукции <tex>UNSAT(G_i) \ge min(2^i UNSAT(G_0), \alpha). Если <tex>UNSAT(G_0)>0</tex>, то <tex>UNSAT(G_0)\ge \frac 1 {|E_0|}</tex>. Конечно, <tex>2^k UNSAT(G_0) > \alpha</tex>. Таким образом <tex>UNSAT(G_k) \ge \alpha</tex>. Мы доказали, что <tex>GAP</tex> <tex>\mathrm{NP}</tex>-трудная. В частности, для <tex>GAP-3SAT</tex>, надо преобразовать каждое условие к константное число дизъюнктов <tex>3CNF</tex>.
}}
==Дополнительные материалы==
