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