Теорема Валианта-Вазирани — различия между версиями

Материал из Викиконспекты
Перейти к: навигация, поиск
(Доказательство теоремы)
м (rollbackEdits.php mass rollback)
 
(не показаны 22 промежуточные версии 3 участников)
Строка 1: Строка 1:
'''Теорема Валианта-Вазирани''' (Valiant–Vazirani theorem) является клевым современным результатом в теории сложности.
+
'''Теорема Валианта-Вазирани''' (Valiant–Vazirani theorem) является важным современным (1986 год) результатом об отношении между сложностными классами.
  
 
===Формулировка теоремы===
 
===Формулировка теоремы===
Строка 7: Строка 7:
 
==Доказательство теоремы==
 
==Доказательство теоремы==
  
Для доказательства этого факта покажем, что по заданной в КНФ формуле <tex>\phi</tex> можно за полиномиальное время построить набор формул <tex>\phi_1 \ldots \phi_m</tex> такой, что:
+
Для доказательства этого факта покажем, что по заданной в КНФ формуле <tex>\phi</tex> можно за полиномиальное время построить набор формул {<tex>\phi_1 \ldots \phi_m</tex>} такой, что:
 
* если формула <tex>\phi</tex> неудовлетворима (то есть не принадлежит '''[[SAT]]'''), то все формулы <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> удовлетворима, то с вероятностью большей ½ в наборе найдется формула <tex>\phi_i</tex> ∈ '''USAT'''.
  
Таким образом задача принадлежности формулы <tex>\phi</tex> языку '''SAT''' будет разрешаться за полиномиальное время с вероятностью односторонней ошибки меньшей ½, то есть '''SAT''' ∈ '''RP''', следовательно, '''NP'''='''RP'''.
+
Таким образом (учитывая, что по условию теоремы включение <tex>\phi_i</tex> ∈ '''USAT''' определяется за полиномиальное время), задача принадлежности формулы <tex>\phi</tex> языку '''SAT''' будет разрешаться за полиномиальное время с вероятностью односторонней ошибки меньшей ½, то есть '''SAT''' ∈ '''RP''', следовательно, '''NP'''='''RP'''.
  
 
===Построение набора формул===
 
===Построение набора формул===
Строка 21: Строка 21:
 
*Выберем равновероятно случайным образом целые числа <tex>p_i</tex> из отрезка [1..<tex>b_i</tex>] и <tex>r_i</tex> из отрезка [0..<tex>b_i</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 \wedge (x \bmod p_i = r_i)</tex>, где выражение <tex>(x \bmod 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>\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>x^{(1)} \ldots x^{(D)}</tex> все выполняющие наборы формулы <tex>\phi</tex>. Заметим, что их число, обозначенное как <tex>D</tex>, нам неизвестно (но не превосходит 2<sup>''n''</sup>).
 +
#Равенство <tex>i = \lceil \log_2 D \rceil</tex> выполняется с вероятностью <tex>\frac{1}{n+1}</tex>, так как <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>\pi(b_i) \approx \frac{b_i}{\log_2 b_i} = \frac{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 - D \cdot n \ge 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>.
 +
#Домножая полученную вероятность на вероятность выбрать подходящее <tex>i</tex> (см. второй пункт), получим, что вероятность верного построения формулы <tex>\phi_k</tex> составляет <tex>1-\frac{1}{32n^3(n+1)}</tex>.
  
*Равенство <tex>i = \lceil \log_2 D \rceil</tex> выполняется с вероятностью 1/(<tex>n</tex>+1), так как <tex>i</tex> было выбрано из [0..<tex>n</tex>]. Предположим, что это соотношение верно.
+
Составив набор {<tex>\phi_1 \ldots \phi_m</tex>} из ''O''(''n''<sup>4</sup>) формул, каждый раз выбирая тройку (<tex>i</tex>, <tex>p_i</tex>, <tex>r_i</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>.
 
  
 
==Внешние ссылки==
 
==Внешние ссылки==

Текущая версия на 19:38, 4 сентября 2022

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

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

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

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

Для доказательства этого факта покажем, что по заданной в КНФ формуле [math]\phi[/math] можно за полиномиальное время построить набор формул {[math]\phi_1 \ldots \phi_m[/math]} такой, что:

  • если формула [math]\phi[/math] неудовлетворима (то есть не принадлежит SAT), то все формулы [math]\phi_1 \ldots \phi_m[/math] также неудовлетворимы;
  • если формула [math]\phi[/math] удовлетворима, то с вероятностью большей ½ в наборе найдется формула [math]\phi_i[/math]USAT.

Таким образом (учитывая, что по условию теоремы включение [math]\phi_i[/math]USAT определяется за полиномиальное время), задача принадлежности формулы [math]\phi[/math] языку SAT будет разрешаться за полиномиальное время с вероятностью односторонней ошибки меньшей ½, то есть SATRP, следовательно, NP=RP.

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

Пусть формуле [math]\phi(x_1 \ldots x_n)[/math] с [math]n[/math] переменными соответствует [math]n[/math]-битное число [math]x[/math], которое кодирует набор переменных.

  • Выберем равновероятно случайным образом целое число [math]i[/math] из отрезка [0..[math]n[/math]]. Определим число [math]b_i = 2^{i + 2}n^2[/math].
  • Выберем равновероятно случайным образом целые числа [math]p_i[/math] из отрезка [1..[math]b_i[/math]] и [math]r_i[/math] из отрезка [0..[math]b_i[/math]].
  • Добавим в набор формулу [math]\phi_k = \phi \wedge (x \bmod p_i = r_i)[/math], где выражение [math](x \bmod p_i = r_i)[/math] в данном случае обозначает булеву запись в КНФ, зависящую от переменных [math]x_1 \ldots x_n[/math] и соответствующую данному сравнению.

Данное построение работает за полиномиальное время, и если формула [math]\phi[/math] невыполнима, то любая формула [math]\phi_k[/math] невыполнима.

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

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

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

  1. Обозначим за [math]x^{(1)} \ldots x^{(D)}[/math] все выполняющие наборы формулы [math]\phi[/math]. Заметим, что их число, обозначенное как [math]D[/math], нам неизвестно (но не превосходит 2n).
  2. Равенство [math]i = \lceil \log_2 D \rceil[/math] выполняется с вероятностью [math]\frac{1}{n+1}[/math], так как [math]i[/math] было выбрано из [0..[math]n[/math]]. Предположим, что это соотношение верно.
  3. Для некоторых [math]x^{(j)}[/math] и [math]x^{(h)}[/math] при условии несовпадения [math]j[/math] и [math]h[/math] имеется не более [math]n[/math] простых делителей разности [math]x^{(j)} - x^{(h)}[/math], так как [math]x^{(j)}[/math] и [math]x^{(h)}[/math] не превосходят 2n.
  4. Из курса теории чисел известно, что для достаточно больших [math]n[/math] имеется не менее [math]\pi(b_i) \approx \frac{b_i}{\log_2 b_i} = \frac{2^{i + 2}n^2}{i + 2 + 2 \log_2 n} \ge 2^{i+1}n[/math] простых чисел, не превосходящих [math]b_i[/math].
  5. Из двух предыдущих рассуждений следует, что существует по крайней мере [math]2^{i+1}n - D \cdot n \ge 2^{i+1}n - 2^{i}n = 2^{i}n[/math] чисел [math]p[/math] таких, что они не превосходят [math]b_i[/math] и остаток от деления [math]x^{(j)}[/math] на [math]p[/math] не совпадает с остатком от деления любого [math]x^{(h)}[/math] на [math]p[/math].
  6. Таким образом по крайней мере [math]2^{i}n[/math] пар чисел [math]0 \le p_l, r_l \le b_i[/math] отличают набор [math]x^{(j)}[/math] от всех остальных. Заметим, что при этом множества пар отличающих чисел ([math]p_l[/math], [math]r_l[/math]) для каждого выполняющего набора переменных [math]x^{(j)}[/math] дизъюнктны.
  7. Следовательно, всего имеется не менее [math]2^i n \cdot D \ge 2^{2i-1}n[/math] искомых отличающих пар. В данной оценке мы использовали равенство из второго пункта.
  8. Таким образом, вероятность выбрать отличающую пару чисел ([math]p_l[/math], [math]r_l[/math]) составляет не менее [math]\frac{2^{2i-1}n}{16\cdot2^{2i}n^4}=\frac{1}{32n^3}[/math].
  9. Домножая полученную вероятность на вероятность выбрать подходящее [math]i[/math] (см. второй пункт), получим, что вероятность верного построения формулы [math]\phi_k[/math] составляет [math]1-\frac{1}{32n^3(n+1)}[/math].

Составив набор {[math]\phi_1 \ldots \phi_m[/math]} из O(n4) формул, каждый раз выбирая тройку ([math]i[/math], [math]p_i[/math], [math]r_i[/math]) чисел случайным образом, получим константную вероятность ошибки. Таким образом необходимый набор формул построен, а теорема доказана.

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

Оригинальная статья 1986 года - Valiant, Leslie G., Vijay Vazirani NP is as easy as detecting unique solutions

Лекция Э.А.Гирша