165
правок
Изменения
→Построение набора формул
*Добавим в набор формулу <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</tex> невыполнима, то любая формула <tex>\phi_k</tex> невыполнима.
===Вероятность существования единственного удовлетворяющего набора===
