165
правок
Изменения
Нет описания правки
* если формула <tex>\phi</tex> удовлетворима, то с вероятностью большей ½ в наборе найдется формула <tex>\phi_i</tex> ∈ '''USAT'''.
Таким образом задача принадлежности формулы языку '''SAT''' будет разрешаться за полиномиальное с вероятностью большей ½, то есть '''SAT''' ∈ '''RP''', следовательно, '''NP'''='''RP'''.
==Внешние ссылки==
