165
правок
Изменения
Нет описания правки
Если язык '''[[USAT]]''' принадлежит классу '''[[P]]''', то классы языков '''[[NP]]''' и '''[[RP]]''' совпадают.
Для доказательства этого факта покажем, что по заданной в КНФ формуле <tex>\phi</tex> можно за полиномиальное время построить набор формул <tex>\phi_1 \ldots \phi_m</tex> такой, что:
* если формула <tex>\phi</tex> удовлетворима, то с вероятностью большей ½ в наборе найдется формула <tex>\phi_i</tex> ∈ '''USAT'''.
Таким образом задача принадлежности формулы языку '''SAT''' будет разрешаться за полиномиальное время с вероятностью большей ½, то есть '''SAT''' ∈ '''RP''', следовательно, '''NP'''='''RP'''. ===Построение набора формул=== Пусть формуле <tex>\phi(x_1 \ldots x_n)</tex> с ''n'' переменными соответствует ''n''-битное число <tex>x</tex>, которое кодирует значения переменных. Выберем равновероятно случайным образом целое число <tex>i</tex> из отрезка [0..''n'']. Определим число <tex>b_i = 2^{i + 2}n^2</tex>. Выберем равновероятно случайным образом целые числа <tex>p_i</tex> из отрезка [1..<tex>b_i</tex>] и <tex>r_i</tex> из отрезка [0..<tex>b_i</tex>]. Добавим в набор формулу <tex>\phi_k = \phi \wedge (x \mod p_i = r_i)</tex>.
==Внешние ссылки==
