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