165
правок
Изменения
Нет описания правки
Пусть формуле <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>, где выражение <tex>(x \mod p_i = r_i)</tex> в данном случае обозначает булеву запись в КНФ, зависящую от переменных <tex>x_1 \ldots x_n</tex> и соответствующую данному сравнению.
Данное построение работает за полиномиальное время и если формула <tex>\phi_k = \phi </tex> невыполнима, то и все формулы <tex>\wedge (x \mod p_i = r_i)phi_k</tex>, невыполнимы.
==Внешние ссылки==
