Изменения

Перейти к: навигация, поиск

Теорема Махэни

6521 байт добавлено, 22:24, 25 апреля 2016
м
Редкие языки
Теорема Махэни, доказанная Стефаном Махэни в 1982 году, утверждает, что если хотя бы один [[#Sparse|редкий язык]] {{---}} [[Сведение_относительно_класса_функций._Сведение_по_Карпу._Трудные_и_полные_задачи#.D0.9E.D0.BF.D1.80.D0.B5.D0.B4.D0.B5.D0.BB.D0.B5.D0.BD.D0.B8.D1.8F_.D1.82.D1.80.D1.83.D0.B4.D0.BD.D1.8B.D1.85_.D0.B8_.D0.BF.D0.BE.D0.BB.D0.BD.D1.8B.D1.85_.D0.B7.D0.B0.D0.B4.D0.B0.D1.87 | <tex> \mathrm{NP} </tex>{{---}}полный ]], то <tex> \mathrm{P} = \mathrm{NP} </tex>
 
==Подготовка к доказательству==
 
Введём вспомогательный язык <tex>\mathrm{LSAT}</tex>.
{{Определение
|definition=
<tex>\mathrm{LSAT} =\{\langle\phivarphi,y\rangle | \mid \exists x: x<_\leqslant_{lex}y, \phivarphi(x) = 1\}</tex>, где <tex> \varphi </tex> {{---}} [[Определение_булевой_функции | булева формула]] из <tex>n</tex> переменных, <tex>x, y \in \{0,1\}^{n} </tex> и отношение <tex> \leqslant_{lex} </tex> задает [[Лексикографический порядок | лексикографический порядок]].
}}
{{Лемма
|about=1|statement=<tex>\mathrm{LSAT } \in \mathrm{NPC}</tex>.
|proof=
#Очевидно, что <tex>\mathrm{LSAT } \in \mathrm{NP}</tex>(в качестве [[Классы_NP,_coNP,_Σ₁,_Π₁#.D0.9E.D0.BF.D1.80.D0.B5.D0.B4.D0.B5.D0.BB.D0.B5.D0.BD.D0.B8.D1.8F.2C_.D1.81.D0.B2.D1.8F.D0.B7.D1.8C_.CE.A3.E2.82.81_.D0.B8_NP|сертификата]] можно запросить <tex>x</tex>).#[[Сведение относительно класса функций. Сведение по Карпу. Трудные и полные задачи | Сведём ]] <tex>\mathrm{SAT}</tex> к <tex>\mathrm{LSAT}</tex>. Для этого рассмотрим отображение <tex>\phi varphi \mapsto \langle \phivarphi, 1^m{|\varphi|}\rangle</tex>, где <tex>m|\varphi|</tex> — количество различных аргументов переменных в формуле <tex>\phivarphi</tex>. Ясно, что данное преобразование можно сделать за полиномиальное время. Теперь докажем, что сведение верное. #*Если <tex>\phi varphi \in \mathrm{SAT}</tex>, то формула <tex>\phivarphi</tex> удовлетворима, а значит <tex>\exists x: x <_\leqslant_{lex} 1^m{|\varphi|}, \phivarphi(x)=1</tex>. Такой <tex> x </tex> cуществует, потому что формула удовлетворима и любой вектор длины <tex> |\varphi| </tex> меньше либо равен единичному, значит мы переберем всевозможые вектора. Следовательно, <tex>\langle \phivarphi, 1^m{|\varphi|}\rangle \in \mathrm{LSAT}</tex>.#*Если <tex>\langle \phivarphi, 1^m{|\varphi|}\rangle \in \mathrm{LSAT}</tex>, то <tex>\exists x: x <_\leqslant_{lex} 1^m{|\varphi|}, \phivarphi(x)=1</tex>. Значит формула <tex>\phivarphi</tex> удовлетворима, и <tex>\phi varphi \in \mathrm{SAT}</tex>.:Таким образом, <tex>\mathrm{SAT } \le leqslant \mathrm{LSAT}</tex>. Но [[Теорема Кука | по теореме Кука ]]<tex>\mathrm{SAT } \in \mathrm{NPC}</tex>, а значит для любого <tex>\forall L \in \mathrm{NP } </tex> выполнено <tex> L \; L leqslant \le mathrm{SAT}</tex>. Тогда в силу транзитивности <tex>\forall L \in \mathrm{NP } \; L \le leqslant \mathrm{LSAT}</tex>, то есть <tex>\mathrm{LSAT } \in \mathrm{NPH}</tex>.Итого , мы доказали, что <tex>\mathrm{LSAT } \in \mathrm{NPH}</tex> и <tex>\mathrm{LSAT } \in \mathrm{NP}</tex>. Тогда по определению <tex>\mathrm{LSAT } \in \mathrm{NPC}</tex>.
}}
{{Лемма
|about=2|statement=<tex>\langle\phivarphi,y\rangle \in \mathrm{LSAT}, y<_{lex}z</tex>. Тогда <tex>\langle\phivarphi,z\rangle \in \mathrm{LSAT}</tex>.|proof=<tex>\langle\phivarphi,y\rangle \in \mathrm{LSAT}</tex>. Тогда <tex>\exists x: x<_\leqslant_{lex}y, \phivarphi(x) = 1</tex>. Так как <tex>y<_{lex}z</tex>, то <tex>\exists x: x<_{lex}z, \phivarphi(x) = 1</tex>, следовательно <tex>\langle\phivarphi,z\rangle \in \mathrm{LSAT}</tex>.}} ==Редкие языки== {{Определение|id = Sparse|definition=<tex>\mathrm{SPARSE}=\{L \mid \exists</tex>полином <tex> p: \forall n \, |L \cap \Sigma^n| \leqslant p(n)\}</tex> {{---}} множество '''редких''' (англ. ''sparse'') языков.
}}
То есть множество языков таких, что множество слов длины <tex> n </tex> из языка ограничено полиномом от <tex> n </tex>.
 
Это множество, называется множеством редких языков потому, что строк длины <tex> n </tex> всего <tex> 2^{n} </tex>, и если язык содержит только полином от этого числа, то при большом <tex> n </tex> эта часть стремится к нулю.
 
'''Пример:''' Согласно [[Машина_Тьюринга#.D0.9C.D0.BD.D0.BE.D0.B3.D0.BE.D0.BB.D0.B5.D0.BD.D1.82.D0.BE.D1.87.D0.BD.D0.B0.D1.8F_.D0.BC.D0.B0.D1.88.D0.B8.D0.BD.D0.B0_.D0.A2.D1.8C.D1.8E.D1.80.D0.B8.D0.BD.D0.B3.D0.B0 | тезису Чёрча {{---}} Тьюринга]], существует биекция между машинами Тьюринга и программами. Зафиксировав алфавит, можно занумеровать программы (программа будет иметь номер <tex>n</tex>, если ее код {{---}} <tex>n</tex>-е слово среди всех слов над алфавитом, отсортированных сначала по возрастанию длины, а при равной длине {{---}} в лексикографическом порядке), а следовательно и машины Тьюринга. Рассмотрим язык <tex> \{1^{n} \mid n</tex>{{---}}я [[Машина Тьюринга | машина Тьюринга]] останавливается в допускающем состоянии <tex> \} </tex>. Просто приняв <tex> p(n) = 1 </tex>, получим, что он принадлежит <tex> \mathrm{SPARSE}</tex>. Более того, любой унарный язык принадлежит <tex>\mathrm{SPARSE} </tex> .
==Теорема==
{{Теорема
|author=Махэни
|statement=
<tex>\mathrm{NPC } \cap \mathrm{SPARSE } \ne \varnothing \Rightarrow \mathrm{P}=\mathrm{NP}</tex>.|proof=Пусть <tex>S \in \mathrm{NPC } \cap \mathrm{SPARSE}</tex>. Так как <tex>S\in \mathrm{NPC}</tex> и <tex>\mathrm{LSAT} \in \mathrm{NPC}</tex>, то существует полиномиальная функция сведения <tex>f</tex> такая, что <tex>\langle \varphi, y \rangle \in \mathrm{LSAT} \Leftrightarrow f(\langle \varphi, y \rangle) \in S</tex>. Так как функция <tex>f</tex> работает полиномиальное время, то <tex>f(\langle\varphi,y\rangle) \leqslant q(|\varphi|)</tex>, где <tex>q</tex> — полином.<tex>S\in \mathrm{SPARSE}</tex>, следовательно <tex>\forall n \; |S \cap \Sigma^n|\leqslant p(n)</tex>, где <tex>p</tex>— некоторый полином.
Так как Тогда <tex>S|\{x\in NPC</tex>, и <tex>LSAT S \in NP</tex>, то существует полиномиальная функция сведения <tex>f:LSAT mid |x| \mapsto S</tex> такая, что <tex>leqslant q(|\langle varphi|)\phi, y }| = \rangle displaystyle\in LSAT sum\iff flimits_{i=1}^{q(|\varphi|)}|S \cap \Sigma^i| \langle leqslant \phi, y displaystyle\sum\limits_{i=1}^{q(|\ranglevarphi|)} p(i) = r(|\in Svarphi|)</tex>, где <tex>r</tex>— также полином.
Так как функция Опишем алгоритм для нахождения лексикографически минимальной строки <tex>fx</tex> работает полиномиальное время, и удовлетворяющей формуле <tex>|\phi|=|y|</tex>, то <tex>f(\langle\phi,y\rangle) \le q(|\phi|)</tex>, где <tex>q</tex> — полином.<tex>S\in SPARSE</tex>. Следовательно <tex>\forall n |S \cap \Sigma^n|\le p(n)</tex>, где <tex>p</tex> — некоторый полином. Тогда <tex>|\{x\in S\, |\, |x| \le q(|\phi|)\}| \le \sum\limits_{i=1}^{q(|\phi|)} p(i) = r(|\phi|)</tex>, где <tex>rvarphi</tex> — также полином.
Опишем алгоритм Пусть <tex>n=|\varphi|, r=r(|\varphi|)</tex>. Изначально область поиска для нахождения лексиграфически минимальной строки <tex>x</tex>, удовлетворяющей формулу — все строки длины <tex>\phin</tex>. Опишем одну итерацию поиска.
Пусть <tex>n=|\phi|</tex>. Разобьём текущее множество бинарных строк длины <tex>n</tex> на <tex>r+1</tex> подотрезок так, чтобы каждый подотрезок содержал не более примерно равной длины. Обозначим концы полученных подотрезков <tex>w_0, \frac{2^n}ldots ,w_{r+1}</tex> строк. Обозначим концы полученных подотрезков И <tex>w_0,...,< w_1 < \ldots < w_{r+1}</tex>. Пусть теперь <tex>z_i=f(\langle\phivarphi,w_i\rangle)</tex>.
Из леммы (2 ) мы знаем, что, начиная с некоторого <tex>il</tex>, все пары <tex>\langle\phivarphi, w_iw_l\rangle \in \mathrm{LSAT}</tex>. Тогда по сведению <tex>z_j \in S</tex> для всех <tex>j\ge igeqslant l</tex>.
Рассмотрим два случая:
# <tex>\exists i \ne j \, z_i=z_j</tex> для некоторого <tex> j > i </tex>. Строки <tex>z_i</tex> и <tex>z_j</tex> либо обе лежат в <tex>S</tex>, либо обе не лежат в <tex>S</tex>. Если <tex>z_i, z_j \in S</tex>, то по сведению <tex> \langle \varphi, w_i \rangle, \langle \varphi, w_j \rangle \in \mathrm{LSAT}</tex>, то есть получаем <tex> x \leqslant w_i < w_j </tex>. Тогда по вышеуказанной причине <tex>x\notin [(w_i, w_j]</tex>. Значит мы можем исключить этот отрезок полуинтервал из рассматриваемого множества. Таким образом, мы удаляем не менее <tex>\frac dfrac 1{r+1}</tex> часть множества подстановок.# <tex>z_i \ne z_j \, \forall i \ne j</tex>. Как было показано выше, если <tex>x \in [w_0</tex> или <tex>, w_1]</tex> лежат в , то все <tex>Sz_i</tex>, то все последующие начиная с <tex>w_iz_1</tex> тоже , лежат в <tex>S</tex>, но тогда <tex>S</tex> содержит не менее <tex>r+1</tex> строку длины не более, чем <tex>q(|\phivarphi|)</tex>, что противоречит условию <tex>|\{x\in S\, |\, mid |x| \le leqslant q(|\phivarphi|)\}| \le leqslant r(|\phivarphi|)</tex>. Следовательно , <tex>x\notin[w_0,w_1]</tex>, то есть его можно убрать из рассмотрения. В обоих случаях мы сузили область поиска как минимум на <tex>\dfrac 1{r+1}</tex> её размера.  Будем повторять эту процедуру до тех пор, пока не останется не более <tex>r+1</tex> строки, которые мы можем проверить за полиномиальное время. Если какая{{---}}то из них удовлетворила формуле <tex>\varphi</tex>, то <tex>x=\min(w_i), w_i</tex> удовлетворяет <tex>\varphi</tex>. Иначе, <tex>x</tex> не существует.
В обоих случаях мы сузили область поиска как минимум на Оценим время работы нашего алгоритма. После <tex>\frac 1{r+1}k</tex> её размера. Будем повторять эту процедуру до тех пор, пока не итераций у нас останется не более <tex>2^n\left(1-\dfrac1{r</tex> строк, которые мы можем проверить за полиномиальное время. Если какая-то из них удовлетворила формулу <tex>+1}\phi</tex>, то <tex>x=min(w_iright), w_i</tex> удовлетворяет <tex>\phi^k</tex>строк. Иначе, Оценим <tex>xk</tex> не существует.
Оценим время работы нашего алгоритма. После <tex>k</tex> итераций у нас останется не более Нам нужно, чтобы <tex>2^n\left(1-\frac1dfrac1{r+1}\right)^k\simeq 1</tex> строк. Оценим Отсюда <tex>k=O(rn)</tex>(это можно получить, выразив <tex>k</tex> через <tex>n</tex> и <tex>r</tex> и воспользовавшись [[Формула Тейлора для произвольной функции | формулой Тейлора]] для логарифма).
<tex>2^n(1-\frac1{r+1})^k \simeq 1</tex>. Отсюда <tex>k=O(rn)</tex>. Таким образом, мы можем разрешить язык <tex>\mathrm{LSAT}</tex> за полиномиальное время, найдя лексиграфически лексикографически минимальную строку, удовлетворяющую формулуформуле, и сравнив её с нашим аргументом. Так как <tex>\mathrm{LSAT}\in \mathrm{NPC}</tex>, то мы можем решить любую задачу из <tex>\mathrm{NP}</tex> за полиномиальное время, а значит <tex>\mathrm{P}=\mathrm{NP}</tex>.
}}
 
== См. также ==
*[[Класс P]]
*[[Классы NP и Σ₁]]
*[[Сведение относительно класса функций. Сведение по Карпу. Трудные и полные задачи]]
*[[Теорема Бермана — Форчуна]]
 
== Источники информации ==
* [http://blog.computationalcomplexity.org/2011/09/mahaneys-theorem.html Блог Computational Complexity]
* [https://en.wikipedia.org/wiki/Sparse_language Wikipedia — Sparse language]
 
[[Категория: Теория сложности]]
[[Категория: Детерминированные и недетерминированные вычисления, сложность по времени и по памяти]]
[[Категория: Классы P и NP, NP{{---}}полнота]]

Навигация