143
правки
Изменения
м
забыл тег
Пусть <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>.
Если <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>.
