165
правок
Изменения
Нет описания правки
* если формула <tex>\phi</tex> удовлетворима, то с вероятностью большей ½ в наборе найдется формула <tex>\phi_i</tex> ∈ '''USAT'''.
Таким образом задача принадлежности формулы <tex>\phi</tex> языку '''SAT''' будет разрешаться за полиномиальное время с вероятностью большей односторонней ошибки меньшей ½, то есть '''SAT''' ∈ '''RP''', следовательно, '''NP'''='''RP'''.
===Построение набора формул===
*Добавим в набор формулу <tex>\phi_k = \phi \wedge (x \mod p_i = r_i)</tex>, где выражение <tex>(x \mod p_i = r_i)</tex> в данном случае обозначает булеву запись в КНФ, зависящую от переменных <tex>x_1 \ldots x_n</tex> и соответствующую данному сравнению.
Данное построение работает за полиномиальное время и если формула <tex>\phi</tex> невыполнима, то и все формулы любая формула <tex>\phi_k</tex> невыполнимыневыполнима.
===Вероятность существования единственного удовлетворяющего набора===
Осталось доказать, что с необходимой нам вероятностью при условии выполнимости <tex>\phi</tex> построенная формула <tex>\phi_k</tex> имеет единственный набор, ее удовлетворяющий.
==Внешние ссылки==
