Теорема Махэни — различия между версиями

Материал из Викиконспекты
Перейти к: навигация, поиск
(См. также)
м (rollbackEdits.php mass rollback)
 
(не показано 19 промежуточных версий 8 участников)
Строка 1: Строка 1:
 +
Теорема Махэни, доказанная Стефаном Махэни в 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=
 
|definition=
<tex>\mathrm{LSAT}=\{\langle\phi,y\rangle \bigm| \exists x: x\le_{lex}y, \phi(x) = 1\}</tex>.
+
<tex>\mathrm{LSAT} = \{\langle \varphi, y \rangle \mid \exists x: x \leqslant_{lex} y, \varphi(x) = 1\}</tex>, где <tex> \varphi </tex> {{---}} [[Определение_булевой_функции | булева формула]] из <tex>n</tex> переменных, <tex>x, y \in \{0,1\}^{n} </tex> и отношение <tex> \leqslant_{lex} </tex> задает [[Лексикографический порядок | лексикографический порядок]].
 
}}
 
}}
  
Строка 8: Строка 13:
 
|statement=<tex>\mathrm{LSAT} \in \mathrm{NPC}</tex>.
 
|statement=<tex>\mathrm{LSAT} \in \mathrm{NPC}</tex>.
 
|proof=
 
|proof=
#Очевидно, что <tex>\mathrm{LSAT} \in \mathrm{NP}</tex> (в качестве сертификата можно запросить <tex>x</tex>).
+
#Очевидно, что <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 \mapsto \langle \phi, 1^{|\phi|}\rangle</tex>, где <tex>|\phi|</tex> — количество различных переменных в формуле <tex>\phi</tex>. Ясно, что данное преобразование можно сделать за полиномиальное время. Теперь докажем, что сведение верное.  
+
#[[Сведение относительно класса функций. Сведение по Карпу. Трудные и полные задачи | Сведём]] <tex>\mathrm{SAT}</tex> к <tex>\mathrm{LSAT}</tex>. Для этого рассмотрим отображение <tex>\varphi \mapsto \langle \varphi, 1^{|\varphi|}\rangle</tex>, где <tex>|\varphi|</tex> — количество различных переменных в формуле <tex>\varphi</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>\varphi \in \mathrm{SAT}</tex>, то формула <tex>\varphi</tex> удовлетворима, а значит <tex>\exists x: x \leqslant_{lex} 1^{|\varphi|}, \varphi(x)=1</tex>. Такой <tex> x </tex> cуществует, потому что формула удовлетворима и любой вектор длины <tex> |\varphi| </tex> меньше либо равен единичному, значит мы переберем всевозможые вектора. Следовательно, <tex>\langle \varphi, 1^{|\varphi|}\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>\langle \varphi, 1^{|\varphi|}\rangle \in \mathrm{LSAT}</tex>, то <tex>\exists x: x \leqslant_{lex} 1^{|\varphi|}, \varphi(x)=1</tex>. Значит формула <tex>\varphi</tex> удовлетворима, и <tex>\varphi \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{SAT} \leqslant \mathrm{LSAT}</tex>. Но [[Теорема Кука | по теореме Кука ]]<tex>\mathrm{SAT} \in \mathrm{NPC}</tex>, а значит для любого <tex>L \in \mathrm{NP} </tex> выполнено <tex> L \leqslant \mathrm{SAT}</tex>. Тогда в силу транзитивности <tex>\forall L \in \mathrm{NP} \; L \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>.
+
Итого, мы доказали, что <tex>\mathrm{LSAT} \in \mathrm{NPH}</tex> и <tex>\mathrm{LSAT} \in \mathrm{NP}</tex>. Тогда по определению <tex>\mathrm{LSAT} \in \mathrm{NPC}</tex>.
 
}}
 
}}
  
 
{{Лемма
 
{{Лемма
 
|about=2
 
|about=2
|statement=<tex>\langle\phi,y\rangle \in \mathrm{LSAT}, y<_{lex}z</tex>. Тогда <tex>\langle\phi,z\rangle \in \mathrm{LSAT}</tex>.
+
|statement=<tex>\langle\varphi,y\rangle \in \mathrm{LSAT}, y<_{lex}z</tex>. Тогда <tex>\langle\varphi,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>.
+
|proof=<tex>\langle\varphi,y\rangle \in \mathrm{LSAT}</tex>. Тогда <tex>\exists x: x\leqslant_{lex}y, \varphi(x) = 1</tex>. Так как <tex>y<_{lex}z</tex>, то <tex>\exists x: x<_{lex}z, \varphi(x) = 1</tex>, следовательно <tex>\langle\varphi,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> .
 +
 +
==Теорема==
  
 
{{Теорема
 
{{Теорема
Строка 29: Строка 48:
 
|proof=Пусть <tex>S \in \mathrm{NPC} \cap \mathrm{SPARSE}</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>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>|\phi|=|y|</tex> (<tex>|y|</tex> — длина вектора <tex>y</tex>), то <tex>f(\langle\phi,y\rangle) \le q(|\phi|)</tex>, где <tex>q</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|\le p(n)</tex>, где <tex>p</tex> — некоторый полином.  
+
<tex>S\in \mathrm{SPARSE}</tex>, следовательно <tex>\forall n \; |S \cap \Sigma^n|\leqslant 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\in S \mid |x| \leqslant q(|\varphi|)\}| = \displaystyle\sum\limits_{i=1}^{q(|\varphi|)}|S \cap \Sigma^i| \leqslant \displaystyle\sum\limits_{i=1}^{q(|\varphi|)} p(i) = r(|\varphi|)</tex>, где <tex>r</tex> — также полином.
  
Опишем алгоритм для нахождения лексикографически минимальной строки <tex>x</tex>, удовлетворяющей формуле <tex>\phi</tex>.
+
Опишем алгоритм для нахождения лексикографически минимальной строки <tex>x</tex>, удовлетворяющей формуле <tex>\varphi</tex>.
  
Пусть <tex>n=|\phi|, r=r(|\phi|)</tex>. Изначально область поиска для <tex>x</tex> — все строки длины <tex>n</tex>. Опишем одну итерацию поиска.
+
Пусть <tex>n=|\varphi|, r=r(|\varphi|)</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>.
+
Разобьём текущее множество строк на <tex>r+1</tex> подотрезок примерно равной длины. Обозначим концы полученных подотрезков <tex>w_0, \ldots ,w_{r+1}</tex>. И <tex>w_0 < w_1 < \ldots < w_{r+1} </tex>. Пусть теперь <tex>z_i=f(\langle\varphi,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>.
+
Из леммы (2) мы знаем, что, начиная с некоторого <tex>l</tex>, все пары <tex>\langle\varphi, w_l\rangle \in \mathrm{LSAT}</tex>. Тогда по сведению <tex>z_j \in S</tex> для всех <tex>j\geqslant 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=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>\dfrac 1{r+1}</tex> часть множества подстановок.
# <tex>z_i \ne z_j \, \forall i \ne j</tex>. Как было показано выше, если <tex>z_0</tex> или <tex>z_1</tex> лежит в <tex>S</tex>, то все последующие <tex>z_i</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>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(|\varphi|)</tex>, что противоречит условию <tex>|\{x\in S \mid |x| \leqslant q(|\varphi|)\}| \leqslant r(|\varphi|)</tex>. Следовательно, <tex>x\notin[w_0,w_1]</tex>, то есть его можно убрать из рассмотрения.
  
В обоих случаях мы сузили область поиска как минимум на <tex>\frac 1{r+1}</tex> её размера.  
+
В обоих случаях мы сузили область поиска как минимум на <tex>\dfrac 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>r+1</tex> строки, которые мы можем проверить за полиномиальное время. Если какая{{---}}то из них удовлетворила формуле <tex>\varphi</tex>, то <tex>x=\min(w_i), w_i</tex> удовлетворяет <tex>\varphi</tex>. Иначе, <tex>x</tex> не существует.
  
Оценим время работы нашего алгоритма. После <tex>k</tex> итераций у нас останется не более <tex>2^n(1-\frac1{r+1})^k</tex> строк. Оценим <tex>k</tex>.
+
Оценим время работы нашего алгоритма. После <tex>k</tex> итераций у нас останется не более <tex>2^n\left(1-\dfrac1{r+1}\right)^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>2^n\left(1-\dfrac1{r+1}\right)^k \simeq 1</tex>. Отсюда <tex>k=O(rn)</tex> (это можно получить, выразив <tex>k</tex> через <tex>n</tex> и <tex>r</tex> и воспользовавшись [[Формула Тейлора для произвольной функции | формулой Тейлора]] для логарифма).  
  
 
Таким образом, мы можем разрешить язык <tex>\mathrm{LSAT}</tex> за полиномиальное время, найдя лексикографически минимальную строку, удовлетворяющую формуле, и сравнив её с нашим аргументом. Так как <tex>\mathrm{LSAT}\in \mathrm{NPC}</tex>, то мы можем решить любую задачу из <tex>\mathrm{NP}</tex> за полиномиальное время, а значит <tex>\mathrm{P}=\mathrm{NP}</tex>.
 
Таким образом, мы можем разрешить язык <tex>\mathrm{LSAT}</tex> за полиномиальное время, найдя лексикографически минимальную строку, удовлетворяющую формуле, и сравнив её с нашим аргументом. Так как <tex>\mathrm{LSAT}\in \mathrm{NPC}</tex>, то мы можем решить любую задачу из <tex>\mathrm{NP}</tex> за полиномиальное время, а значит <tex>\mathrm{P}=\mathrm{NP}</tex>.
Строка 66: Строка 85:
 
*[[Сведение относительно класса функций. Сведение по Карпу. Трудные и полные задачи]]
 
*[[Сведение относительно класса функций. Сведение по Карпу. Трудные и полные задачи]]
 
*[[Теорема Бермана — Форчуна]]
 
*[[Теорема Бермана — Форчуна]]
 +
 +
== Источники информации ==
 +
* [http://blog.computationalcomplexity.org/2011/09/mahaneys-theorem.html Блог Computational Complexity]
 +
* [https://en.wikipedia.org/wiki/Sparse_language Wikipedia — Sparse language]
  
 
[[Категория: Теория сложности]]
 
[[Категория: Теория сложности]]
 +
[[Категория: Детерминированные и недетерминированные вычисления, сложность по времени и по памяти]]
 +
[[Категория: Классы P и NP, NP{{---}}полнота]]

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

Теорема Махэни, доказанная Стефаном Махэни в 1982 году, утверждает, что если хотя бы один редкий язык [math] \mathrm{NP} [/math]—полный , то [math] \mathrm{P} = \mathrm{NP} [/math]

Подготовка к доказательству

Введём вспомогательный язык [math]\mathrm{LSAT}[/math].

Определение:
[math]\mathrm{LSAT} = \{\langle \varphi, y \rangle \mid \exists x: x \leqslant_{lex} y, \varphi(x) = 1\}[/math], где [math] \varphi [/math] булева формула из [math]n[/math] переменных, [math]x, y \in \{0,1\}^{n} [/math] и отношение [math] \leqslant_{lex} [/math] задает лексикографический порядок.


Лемма (1):
[math]\mathrm{LSAT} \in \mathrm{NPC}[/math].
Доказательство:
[math]\triangleright[/math]
  1. Очевидно, что [math]\mathrm{LSAT} \in \mathrm{NP}[/math] (в качестве сертификата можно запросить [math]x[/math]).
  2. Сведём [math]\mathrm{SAT}[/math] к [math]\mathrm{LSAT}[/math]. Для этого рассмотрим отображение [math]\varphi \mapsto \langle \varphi, 1^{|\varphi|}\rangle[/math], где [math]|\varphi|[/math] — количество различных переменных в формуле [math]\varphi[/math]. Ясно, что данное преобразование можно сделать за полиномиальное время. Теперь докажем, что сведение верное.
    • Если [math]\varphi \in \mathrm{SAT}[/math], то формула [math]\varphi[/math] удовлетворима, а значит [math]\exists x: x \leqslant_{lex} 1^{|\varphi|}, \varphi(x)=1[/math]. Такой [math] x [/math] cуществует, потому что формула удовлетворима и любой вектор длины [math] |\varphi| [/math] меньше либо равен единичному, значит мы переберем всевозможые вектора. Следовательно, [math]\langle \varphi, 1^{|\varphi|}\rangle \in \mathrm{LSAT}[/math].
    • Если [math]\langle \varphi, 1^{|\varphi|}\rangle \in \mathrm{LSAT}[/math], то [math]\exists x: x \leqslant_{lex} 1^{|\varphi|}, \varphi(x)=1[/math]. Значит формула [math]\varphi[/math] удовлетворима, и [math]\varphi \in \mathrm{SAT}[/math].
Таким образом, [math]\mathrm{SAT} \leqslant \mathrm{LSAT}[/math]. Но по теореме Кука [math]\mathrm{SAT} \in \mathrm{NPC}[/math], а значит для любого [math]L \in \mathrm{NP} [/math] выполнено [math] L \leqslant \mathrm{SAT}[/math]. Тогда в силу транзитивности [math]\forall L \in \mathrm{NP} \; L \leqslant \mathrm{LSAT}[/math], то есть [math]\mathrm{LSAT} \in \mathrm{NPH}[/math].
Итого, мы доказали, что [math]\mathrm{LSAT} \in \mathrm{NPH}[/math] и [math]\mathrm{LSAT} \in \mathrm{NP}[/math]. Тогда по определению [math]\mathrm{LSAT} \in \mathrm{NPC}[/math].
[math]\triangleleft[/math]
Лемма (2):
[math]\langle\varphi,y\rangle \in \mathrm{LSAT}, y\lt _{lex}z[/math]. Тогда [math]\langle\varphi,z\rangle \in \mathrm{LSAT}[/math].
Доказательство:
[math]\triangleright[/math]
[math]\langle\varphi,y\rangle \in \mathrm{LSAT}[/math]. Тогда [math]\exists x: x\leqslant_{lex}y, \varphi(x) = 1[/math]. Так как [math]y\lt _{lex}z[/math], то [math]\exists x: x\lt _{lex}z, \varphi(x) = 1[/math], следовательно [math]\langle\varphi,z\rangle \in \mathrm{LSAT}[/math].
[math]\triangleleft[/math]

Редкие языки

Определение:
[math]\mathrm{SPARSE}=\{L \mid \exists[/math] полином [math] p: \forall n \, |L \cap \Sigma^n| \leqslant p(n)\}[/math] — множество редких (англ. sparse) языков.

То есть множество языков таких, что множество слов длины [math] n [/math] из языка ограничено полиномом от [math] n [/math].

Это множество, называется множеством редких языков потому, что строк длины [math] n [/math] всего [math] 2^{n} [/math], и если язык содержит только полином от этого числа, то при большом [math] n [/math] эта часть стремится к нулю.

Пример: Согласно тезису Чёрча — Тьюринга, существует биекция между машинами Тьюринга и программами. Зафиксировав алфавит, можно занумеровать программы (программа будет иметь номер [math]n[/math], если ее код — [math]n[/math]-е слово среди всех слов над алфавитом, отсортированных сначала по возрастанию длины, а при равной длине — в лексикографическом порядке), а следовательно и машины Тьюринга. Рассмотрим язык [math] \{1^{n} \mid n[/math]—я машина Тьюринга останавливается в допускающем состоянии [math] \} [/math]. Просто приняв [math] p(n) = 1 [/math], получим, что он принадлежит [math] \mathrm{SPARSE}[/math]. Более того, любой унарный язык принадлежит [math]\mathrm{SPARSE} [/math] .

Теорема

Теорема (Махэни):
[math]\mathrm{NPC} \cap \mathrm{SPARSE} \ne \varnothing \Rightarrow \mathrm{P}=\mathrm{NP}[/math].
Доказательство:
[math]\triangleright[/math]

Пусть [math]S \in \mathrm{NPC} \cap \mathrm{SPARSE}[/math].

Так как [math]S\in \mathrm{NPC}[/math] и [math]\mathrm{LSAT} \in \mathrm{NPC}[/math], то существует полиномиальная функция сведения [math]f[/math] такая, что [math]\langle \varphi, y \rangle \in \mathrm{LSAT} \Leftrightarrow f(\langle \varphi, y \rangle) \in S[/math].

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

Тогда [math]|\{x\in S \mid |x| \leqslant q(|\varphi|)\}| = \displaystyle\sum\limits_{i=1}^{q(|\varphi|)}|S \cap \Sigma^i| \leqslant \displaystyle\sum\limits_{i=1}^{q(|\varphi|)} p(i) = r(|\varphi|)[/math], где [math]r[/math] — также полином.

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

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

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

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

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

  1. [math]z_i=z_j[/math] для некоторого [math] j \gt i [/math] . Строки [math]z_i[/math] и [math]z_j[/math] либо обе лежат в [math]S[/math], либо обе не лежат в [math]S[/math]. Если [math]z_i, z_j \in S[/math], то по сведению [math] \langle \varphi, w_i \rangle, \langle \varphi, w_j \rangle \in \mathrm{LSAT}[/math], то есть получаем [math] x \leqslant w_i \lt w_j [/math]. Тогда по вышеуказанной причине [math]x\notin (w_i, w_j][/math]. Значит мы можем исключить этот полуинтервал из рассматриваемого множества. Таким образом, мы удаляем не менее [math]\dfrac 1{r+1}[/math] часть множества подстановок.
  2. [math]z_i \ne z_j \, \forall i \ne j[/math]. Как было показано выше, если [math]x \in [w_0, w_1][/math], то все [math]z_i[/math], начиная с [math]z_1[/math], лежат в [math]S[/math], но тогда [math]S[/math] содержит [math]r+1[/math] строку длины не более, чем [math]q(|\varphi|)[/math], что противоречит условию [math]|\{x\in S \mid |x| \leqslant q(|\varphi|)\}| \leqslant r(|\varphi|)[/math]. Следовательно, [math]x\notin[w_0,w_1][/math], то есть его можно убрать из рассмотрения.

В обоих случаях мы сузили область поиска как минимум на [math]\dfrac 1{r+1}[/math] её размера.

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

Оценим время работы нашего алгоритма. После [math]k[/math] итераций у нас останется не более [math]2^n\left(1-\dfrac1{r+1}\right)^k[/math] строк. Оценим [math]k[/math].

Нам нужно, чтобы [math]2^n\left(1-\dfrac1{r+1}\right)^k \simeq 1[/math]. Отсюда [math]k=O(rn)[/math] (это можно получить, выразив [math]k[/math] через [math]n[/math] и [math]r[/math] и воспользовавшись формулой Тейлора для логарифма).

Таким образом, мы можем разрешить язык [math]\mathrm{LSAT}[/math] за полиномиальное время, найдя лексикографически минимальную строку, удовлетворяющую формуле, и сравнив её с нашим аргументом. Так как [math]\mathrm{LSAT}\in \mathrm{NPC}[/math], то мы можем решить любую задачу из [math]\mathrm{NP}[/math] за полиномиальное время, а значит [math]\mathrm{P}=\mathrm{NP}[/math].
[math]\triangleleft[/math]

См. также

Источники информации