165
правок
Изменения
Нет описания правки
===Построение набора формул===
Пусть формуле <tex>\phi(x_1 \ldots x_n)</tex> с ''<tex>n'' </tex> переменными соответствует ''<tex>n''</tex>-битное число <tex>x</tex>, которое кодирует значения набор переменных.
*Выберем равновероятно случайным образом целое число <tex>i</tex> из отрезка [0..''<tex>n''</tex>]. Определим число <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</tex> построенная формула <tex>\phi_k</tex> имеет единственный набор, ее удовлетворяющий.
Дальнейшие рассуждения рекомендуется читать медленно и внимательно:
*Обозначим за <tex>x^{(1)} \ldots x^{(D)}</tex> все выполняющие наборы формулы <tex>\phi</tex>. Заметим, что их число, обозначенное как <tex>D</tex>, нам неизвестно (но не превосходит 2<sup>''n''</sup>).
==Внешние ссылки==
