Викиконспекты - Вклад участника [ru]

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

2012-06-05T14:58:37Z

178.178.27.55:

Введём вспомогательный язык <tex>\mathrm{LSAT}</tex>.
{{Определение
|definition=
<tex>\mathrm{LSAT}=\{\langle\phi,y\rangle \bigm| \exists x: x\le_{lex}y, \phi(x) = 1\}</tex>.
}}

{{Лемма
|about=1
|statement=<tex>\mathrm{LSAT} \in \mathrm{NPC}</tex>.
|proof=
#Очевидно, что <tex>\mathrm{LSAT} \in \mathrm{NP}</tex> (в качестве сертификата можно запросить <tex>x</tex>).
#Сведём <tex>\mathrm{SAT}</tex> к <tex>\mathrm{LSAT}</tex>. Для этого рассмотрим отображение <tex>\phi \mapsto \langle \phi, 1^{|\phi|}\rangle</tex>, где <tex>|\phi|</tex> — количество различных переменных в формуле <tex>\phi</tex>. Ясно, что данное преобразование можно сделать за полиномиальное время. Теперь докажем, что сведение верное.
#*Если <tex>\phi \in \mathrm{SAT}</tex>, то формула <tex>\phi</tex> удовлетворима, а значит <tex>\exists x: x \le_{lex} 1^{|\phi|}, \phi(x)=1</tex>. Следовательно, <tex>\langle \phi, 1^{|\phi|}\rangle \in \mathrm{LSAT}</tex>.
#*Если <tex>\langle \phi, 1^{|\phi|}\rangle \in \mathrm{LSAT}</tex>, то <tex>\exists x: x \le_{lex} 1^{|\phi|}, \phi(x)=1</tex>. Значит формула <tex>\phi</tex> удовлетворима, и <tex>\phi \in \mathrm{SAT}</tex>.
:Таким образом, <tex>\mathrm{SAT} \le \mathrm{LSAT}</tex>. Но <tex>\mathrm{SAT} \in \mathrm{NPC}</tex>, а значит <tex>\forall L \in \mathrm{NP} \; L \le \mathrm{SAT}</tex>. Тогда в силу транзитивности <tex>\forall L \in \mathrm{NP} \; L \le \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\phi,y\rangle \in \mathrm{LSAT}, y<_{lex}z</tex>. Тогда <tex>\langle\phi,z\rangle \in \mathrm{LSAT}</tex>.
|proof=<tex>\langle\phi,y\rangle \in \mathrm{LSAT}</tex>. Тогда <tex>\exists x: x\le_{lex}y, \phi(x) = 1</tex>. Так как <tex>y<_{lex}z</tex>, то <tex>\exists x: x<_{lex}z, \phi(x) = 1</tex>, следовательно <tex>\langle\phi,z\rangle \in \mathrm{LSAT}</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{NP}</tex>, то существует полиномиальная функция сведения <tex>f</tex> такая, что <tex>\langle \phi, y \rangle \in \mathrm{LSAT} \Leftrightarrow f(\langle \phi, y \rangle) \in S</tex>.

Так как функция <tex>f</tex> работает полиномиальное время, и <tex>|\phi|=|y|</tex> (<tex>|y|</tex> — длина вектора <tex>y</tex>), то <tex>f(\langle\phi,y\rangle) \le q(|\phi|)</tex>, где <tex>q</tex> — полином.
<tex>S\in \mathrm{SPARSE}</tex>, следовательно <tex>\forall n \; |S \cap \Sigma^n|\le p(n)</tex>, где <tex>p</tex> — некоторый полином.

Тогда <tex>|\{x\in S \bigm| |x| \le q(|\phi|)\}| \le \sum\limits_{i=1}^{q(|\phi|)} p(i) = r(|\phi|)</tex>, где <tex>r</tex> — также полином.

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

Пусть <tex>n=|\phi|, r=r(|\phi|)</tex>. Изначально область поиска для <tex>x</tex> — все строки длины <tex>n</tex>. Опишем одну итерацию поиска.

Разобьём текущее множество строк на <tex>r+1</tex> подотрезок примерно равной длины. Обозначим концы полученных подотрезков <tex>w_0,...,w_{r+1}</tex>. Пусть теперь <tex>z_i=f(\langle\phi,w_i\rangle)</tex>.

Из леммы (2) мы знаем, что, начиная с некоторого <tex>l</tex>, все пары <tex>\langle\phi, w_l\rangle \in \mathrm{LSAT}</tex>. Тогда по сведению <tex>z_j \in S</tex> для всех <tex>j\ge l</tex>.

Рассмотрим два случая:

# <tex>\exists i \ne j : z_i=z_j</tex>. Строки <tex>z_i</tex> и <tex>z_j</tex> либо обе лежат в <tex>S</tex>, либо обе не лежат в <tex>S</tex>. Тогда по вышеуказанной причине <tex>x\notin (w_i, w_j]</tex>. Значит мы можем исключить этот полуинтервал из рассматриваемого множества. Таким образом, мы удаляем не менее <tex>\frac 1{r+1}</tex> часть множества подстановок.
# <tex>z_i \ne z_j \, \forall i \ne j</tex>. Как было показано выше, если <tex>x \in [w_0, w_1]</tex>, то все <tex>z_i</tex>, начиная с <tex>z_1</tex>, лежат в <tex>S</tex>, но тогда <tex>S</tex> содержит <tex>r+1</tex> строку длины не более, чем <tex>q(|\phi|)</tex>, что противоречит условию <tex>|\{x\in S\, |\, |x| \le q(|\phi|)\}| \le r(|\phi|)</tex>. Следовательно, <tex>x\notin[w_0,w_1]</tex>, то есть его можно убрать из рассмотрения.

В обоих случаях мы сузили область поиска как минимум на <tex>\frac 1{r+1}</tex> её размера.

Будем повторять эту процедуру до тех пор, пока не останется не более <tex>r+1</tex> строки, которые мы можем проверить за полиномиальное время. Если какая-то из них удовлетворила формуле <tex>\phi</tex>, то <tex>x=min(w_i), w_i</tex> удовлетворяет <tex>\phi</tex>. Иначе, <tex>x</tex> не существует.

Оценим время работы нашего алгоритма. После <tex>k</tex> итераций у нас останется не более <tex>2^n(1-\frac1{r+1})^k</tex> строк. Оценим <tex>k</tex>.

<tex>2^n(1-\frac1{r+1})^k \simeq 1</tex>. Отсюда <tex>k=O(rn)</tex> (это можно получить, выразив <tex>k</tex> через <tex>n</tex> и <tex>r</tex> и воспользовавшись [http://ru.wikipedia.org/wiki/Ряд_Тейлора#.D0.A0.D1.8F.D0.B4.D1.8B_.D0.9C.D0.B0.D0.BA.D0.BB.D0.BE.D1.80.D0.B5.D0.BD.D0.B0_.D0.BD.D0.B5.D0.BA.D0.BE.D1.82.D0.BE.D1.80.D1.8B.D1.85_.D1.84.D1.83.D0.BD.D0.BA.D1.86.D0.B8.D0.B9 формулой Тейлора] для логарифма).

Таким образом, мы можем разрешить язык <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]

[[Категория: Теория сложности]]

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

2012-06-05T14:56:56Z

178.178.27.55:

Введём вспомогательный язык <tex>\mathrm{LSAT}</tex>.
{{Определение
|definition=
<tex>\mathrm{LSAT}=\{\langle\phi,y\rangle \bigm| \exists x: x\le_{lex}y, \phi(x) = 1\}</tex>.
}}

{{Лемма
|about=1
|statement=<tex>\mathrm{LSAT} \in \mathrm{NPC}</tex>.
|proof=
#Очевидно, что <tex>\mathrm{LSAT} \in \mathrm{NP}</tex> (в качестве сертификата можно запросить <tex>x</tex>).
#Сведём <tex>\mathrm{SAT}</tex> к <tex>\mathrm{LSAT}</tex>. Для этого рассмотрим отображение <tex>\phi \mapsto \langle \phi, 1^{|\phi|}\rangle</tex>, где <tex>|\phi|</tex> — количество различных переменных в формуле <tex>\phi</tex>. Ясно, что данное преобразование можно сделать за полиномиальное время. Теперь докажем, что сведение верное.
#*Если <tex>\phi \in \mathrm{SAT}</tex>, то формула <tex>\phi</tex> удовлетворима, а значит <tex>\exists x: x \le_{lex} 1^{|\phi|}, \phi(x)=1</tex>. Следовательно, <tex>\langle \phi, 1^{|\phi|}\rangle \in \mathrm{LSAT}</tex>.
#*Если <tex>\langle \phi, 1^{|\phi|}\rangle \in \mathrm{LSAT}</tex>, то <tex>\exists x: x \le_{lex} 1^{|\phi|}, \phi(x)=1</tex>. Значит формула <tex>\phi</tex> удовлетворима, и <tex>\phi \in \mathrm{SAT}</tex>.
:Таким образом, <tex>\mathrm{SAT} \le \mathrm{LSAT}</tex>. Но <tex>\mathrm{SAT} \in \mathrm{NPC}</tex>, а значит <tex>\forall L \in \mathrm{NP} \; L \le \mathrm{SAT}</tex>. Тогда в силу транзитивности <tex>\forall L \in \mathrm{NP} \; L \le \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\phi,y\rangle \in \mathrm{LSAT}, y<_{lex}z</tex>. Тогда <tex>\langle\phi,z\rangle \in \mathrm{LSAT}</tex>.
|proof=<tex>\langle\phi,y\rangle \in \mathrm{LSAT}</tex>. Тогда <tex>\exists x: x\le_{lex}y, \phi(x) = 1</tex>. Так как <tex>y<_{lex}z</tex>, то <tex>\exists x: x<_{lex}z, \phi(x) = 1</tex>, следовательно <tex>\langle\phi,z\rangle \in \mathrm{LSAT}</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{NP}</tex>, то существует полиномиальная функция сведения <tex>f</tex> такая, что <tex>\langle \phi, y \rangle \in \mathrm{LSAT} \Leftrightarrow f(\langle \phi, y \rangle) \in S</tex>.

Так как функция <tex>f</tex> работает полиномиальное время, и <tex>|\phi|=|y|</tex> (<tex>|y|</tex> — длина вектора <tex>y</tex>), то <tex>f(\langle\phi,y\rangle) \le q(|\phi|)</tex>, где <tex>q</tex> — полином.
<tex>S\in \mathrm{SPARSE}</tex>, следовательно <tex>\forall n \; |S \cap \Sigma^n|\le p(n)</tex>, где <tex>p</tex> — некоторый полином.

Тогда <tex>|\{x\in S \bigm| |x| \le q(|\phi|)\}| \le \sum\limits_{i=1}^{q(|\phi|)} p(i) = r(|\phi|)</tex>, где <tex>r</tex> — также полином.

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

Пусть <tex>n=|\phi|, r=r(|\phi|)</tex>. Изначально область поиска для <tex>x</tex> — все строки длины <tex>n</tex>. Опишем одну итерацию поиска.

Разобьём текущее множество строк на <tex>r+1</tex> подотрезок примерно равной длины. Обозначим концы полученных подотрезков <tex>w_0,...,w_{r+1}</tex>. Пусть теперь <tex>z_i=f(\langle\phi,w_i\rangle)</tex>.

Из леммы (2) мы знаем, что, начиная с некоторого <tex>l</tex>, все пары <tex>\langle\phi, w_l\rangle \in \mathrm{LSAT}</tex>. Тогда по сведению <tex>z_j \in S</tex> для всех <tex>j\ge l</tex>.

Рассмотрим два случая:

# <tex>\exists i \ne j : z_i=z_j</tex>. Строки <tex>z_i</tex> и <tex>z_j</tex> либо обе лежат в <tex>S</tex>, либо обе не лежат в <tex>S</tex>. Тогда по вышеуказанной причине <tex>x\notin (w_i, w_j]</tex>. Значит мы можем исключить этот полуинтервал из рассматриваемого множества. Таким образом, мы удаляем не менее <tex>\frac 1{r+1}</tex> часть множества подстановок.
# <tex>z_i \ne z_j \, \forall i \ne j</tex>. Как было показано выше, если <tex>x \in [w_0, w_1]</tex>, то все <tex>z_i</tex>, начиная с <tex>z_1</tex> лежат в <tex>S</tex>, но тогда <tex>S</tex> содержит <tex>r+1</tex> строку длины не более, чем <tex>q(|\phi|)</tex>, что противоречит условию <tex>|\{x\in S\, |\, |x| \le q(|\phi|)\}| \le r(|\phi|)</tex>. Следовательно, <tex>x\notin[w_0,w_1]</tex>, то есть его можно убрать из рассмотрения.

В обоих случаях мы сузили область поиска как минимум на <tex>\frac 1{r+1}</tex> её размера.

Будем повторять эту процедуру до тех пор, пока не останется не более <tex>r+1</tex> строки, которые мы можем проверить за полиномиальное время. Если какая-то из них удовлетворила формуле <tex>\phi</tex>, то <tex>x=min(w_i), w_i</tex> удовлетворяет <tex>\phi</tex>. Иначе, <tex>x</tex> не существует.

Оценим время работы нашего алгоритма. После <tex>k</tex> итераций у нас останется не более <tex>2^n(1-\frac1{r+1})^k</tex> строк. Оценим <tex>k</tex>.

<tex>2^n(1-\frac1{r+1})^k \simeq 1</tex>. Отсюда <tex>k=O(rn)</tex> (это можно получить, выразив <tex>k</tex> через <tex>n</tex> и <tex>r</tex> и воспользовавшись [http://ru.wikipedia.org/wiki/Ряд_Тейлора#.D0.A0.D1.8F.D0.B4.D1.8B_.D0.9C.D0.B0.D0.BA.D0.BB.D0.BE.D1.80.D0.B5.D0.BD.D0.B0_.D0.BD.D0.B5.D0.BA.D0.BE.D1.82.D0.BE.D1.80.D1.8B.D1.85_.D1.84.D1.83.D0.BD.D0.BA.D1.86.D0.B8.D0.B9 формулой Тейлора] для логарифма).

Таким образом, мы можем разрешить язык <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]

[[Категория: Теория сложности]]