Просмотр исходного текста страницы Теорема Валианта-Вазирани

'''Теорема Валианта-Вазирани''' (Valiant–Vazirani theorem) является клевым современным результатом в теории сложности.

===Формулировка теоремы===

Если язык '''[[USAT]]''' принадлежит классу '''[[P]]''', то классы языков '''[[NP]]''' и '''[[RP]]''' совпадают.

==Доказательство теоремы==

Для доказательства этого факта покажем, что по заданной в КНФ формуле <tex>\phi</tex> можно за полиномиальное время построить набор формул <tex>\phi_1 \ldots \phi_m</tex> такой, что:
* если формула <tex>\phi</tex> неудовлетворима (то есть не принадлежит '''[[SAT]]'''), то все формулы <tex>\phi_1 \ldots \phi_m</tex> также неудовлетворимы;
* если формула <tex>\phi</tex> удовлетворима, то с вероятностью большей ½ в наборе найдется формула <tex>\phi_i</tex> ∈ '''USAT'''.

Таким образом задача принадлежности формулы <tex>\phi</tex> языку '''SAT''' будет разрешаться за полиномиальное время с вероятностью односторонней ошибки меньшей ½, то есть '''SAT''' ∈ '''RP''', следовательно, '''NP'''='''RP'''.

===Построение набора формул===

Пусть формуле <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_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> невыполнима.

===Вероятность существования единственного удовлетворяющего набора===

Осталось доказать, что с необходимой нам вероятностью при условии выполнимости <tex>\phi</tex> построенная формула <tex>\phi_k</tex> имеет единственный набор, ее удовлетворяющий.

Дальнейшие рассуждения рекомендуется читать медленно и внимательно:

*Обозначим за <tex>x^{(1)} \ldots x^{(D)}</tex> все выполняющие наборы формулы <tex>\phi</tex>. Заметим, что их число, обозначенное как <tex>D</tex>, нам неизвестно (но не превосходит 2<sup>''n''</sup>).

*Равенство <tex>i = \lceil \log_2 D \rceil</tex> выполняется с вероятностью 1/(<tex>n</tex>+1), так как <tex>i</tex> было выбрано из [0..<tex>n</tex>]. Предположим, что это соотношение верно.

*Для некоторых <tex>x^{(j)}</tex> и <tex>x^{(h)}</tex> при условии несовпадения <tex>j</tex> и <tex>h</tex> имеется не более <tex>n</tex> простых делителей разности <tex>x^{(j)} - x^{(h)}</tex>, так как <tex>x^{(j)}</tex> и <tex>x^{(h)}</tex> не превосходят 2<sup>''n''</sup>.

*Из курса теории чисел известно, что для достаточно больших <tex>n</tex> имеется не менее <tex>b_i / \log_2 b_i = 2^{i + 2}n^2 / (i + 2 + 2 \log_2 n) \ge 2^{i+1}n</tex> простых чисел, не превосходящих <tex>b_i</tex>.

*Из двух предыдущих рассуждений следует, что существует по крайней мере <tex>2^{i+1}n - 2^{i}n = 2^{i}n</tex> чисел <tex>p</tex> таких, что они не превосходят <tex>b_i</tex> и остаток от деления <tex>x^{(j)}</tex> на <tex>p</tex> не совпадает с остатком от деления любого <tex>x^{(h)}</tex> на <tex>p</tex>. 

*Таким образом по крайней мере <tex>2^{i}n</tex> пар чисел <tex>0 \le p_l, r_l \le b_i</tex> отличают набор <tex>x^{(j)}</tex> от всех остальных. Заметим, что при этом множества пар отличающих чисел (<tex>p_l</tex>, <tex>r_l</tex>) для каждого выполняющего набора переменных <tex>x^{(j)}</tex> дизъюнктны.

*Следовательно, всего имеется не менее <tex>2^i n \cdot D \ge 2^{2i-1}n</tex> искомых отличающих пар. В данной оценке мы использовали равенство из второго пункта.

*Таким образом вероятность выбрать отличающую пару чисел (<tex>p_l</tex>, <tex>r_l</tex>) составляет не менее <tex>\frac{2^{2i-1}n}{16\cdot2^{2i}n^4}=\frac{1}{32n^3}</tex>.

==Внешние ссылки==

[http://www.cs.princeton.edu/courses/archive/fall05/cos528/handouts/NP_is_as.pdf Оригинальная статья 1986 года - Valiant, Leslie G., Vijay Vazirani NP is as easy as detecting unique solutions]

[http://logic.pdmi.ras.ru/~hirsch/students/complexity1/lecture7.pdf Лекция Э.А.Гирша]