Теорема Валианта-Вазирани — различия между версиями
Ulyantsev (обсуждение | вклад) |
м (rollbackEdits.php mass rollback) |
||
(не показаны 24 промежуточные версии 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 \ | + | *Добавим в набор формулу <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>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>\phi_1 \ldots \phi_m</tex>} из ''O''(''n''<sup>4</sup>) формул, каждый раз выбирая тройку (<tex>i</tex>, <tex>p_i</tex>, <tex>r_i</tex>) чисел случайным образом, получим константную вероятность ошибки. Таким образом необходимый набор формул построен, а теорема доказана. | ||
==Внешние ссылки== | ==Внешние ссылки== |
Текущая версия на 19:38, 4 сентября 2022
Теорема Валианта-Вазирани (Valiant–Vazirani theorem) является важным современным (1986 год) результатом об отношении между сложностными классами.
Содержание
Формулировка теоремы
Если язык USAT принадлежит классу P, то классы языков NP и RP совпадают.
Доказательство теоремы
Для доказательства этого факта покажем, что по заданной в КНФ формуле
можно за полиномиальное время построить набор формул { } такой, что:- если формула SAT), то все формулы также неудовлетворимы; неудовлетворима (то есть не принадлежит
- если формула удовлетворима, то с вероятностью большей ½ в наборе найдется формула ∈ USAT.
Таким образом (учитывая, что по условию теоремы включение
∈ USAT определяется за полиномиальное время), задача принадлежности формулы языку SAT будет разрешаться за полиномиальное время с вероятностью односторонней ошибки меньшей ½, то есть SAT ∈ RP, следовательно, NP=RP.Построение набора формул
Пусть формуле
с переменными соответствует -битное число , которое кодирует набор переменных.- Выберем равновероятно случайным образом целое число из отрезка [0.. ]. Определим число .
- Выберем равновероятно случайным образом целые числа из отрезка [1.. ] и из отрезка [0.. ].
- Добавим в набор формулу , где выражение в данном случае обозначает булеву запись в КНФ, зависящую от переменных и соответствующую данному сравнению.
Данное построение работает за полиномиальное время, и если формула
невыполнима, то любая формула невыполнима.Вероятность существования единственного удовлетворяющего набора
Осталось доказать, что с необходимой нам вероятностью при условии выполнимости
каждая построенная формула имеет единственный набор, ее удовлетворяющий.Дальнейшие рассуждения рекомендуется читать медленно и внимательно:
- Обозначим за все выполняющие наборы формулы . Заметим, что их число, обозначенное как , нам неизвестно (но не превосходит 2n).
- Равенство выполняется с вероятностью , так как было выбрано из [0.. ]. Предположим, что это соотношение верно.
- Для некоторых и при условии несовпадения и имеется не более простых делителей разности , так как и не превосходят 2n.
- Из курса теории чисел известно, что для достаточно больших имеется не менее простых чисел, не превосходящих .
- Из двух предыдущих рассуждений следует, что существует по крайней мере чисел таких, что они не превосходят и остаток от деления на не совпадает с остатком от деления любого на .
- Таким образом по крайней мере пар чисел отличают набор от всех остальных. Заметим, что при этом множества пар отличающих чисел ( , ) для каждого выполняющего набора переменных дизъюнктны.
- Следовательно, всего имеется не менее искомых отличающих пар. В данной оценке мы использовали равенство из второго пункта.
- Таким образом, вероятность выбрать отличающую пару чисел ( , ) составляет не менее .
- Домножая полученную вероятность на вероятность выбрать подходящее (см. второй пункт), получим, что вероятность верного построения формулы составляет .
Составив набор {
} из O(n4) формул, каждый раз выбирая тройку ( , , ) чисел случайным образом, получим константную вероятность ошибки. Таким образом необходимый набор формул построен, а теорема доказана.