Изменения
→Теорема о двух эквивалентных определениях NP (NP = Sigma1)
}}
== Видимо, это про NP-полные задачи полная задача ==
{{Определение
|definition =
<tex>\mathrm{NPC}</tex> является одним из важнейших классов в теории сложности, так как если найдется язык из этого класса, который также входит в класс <tex>\mathrm{P}</tex>,
тогда окажется, что <tex>\mathrm{P} = \mathrm{NP}</tex>.
<tex> \mathrm{BH_{1N}} </tex> {{---}} язык троек <tex> \langle m, x, 1^t \rangle </tex>, таких что недетерминированная машина Тьюринга <tex> m </tex> на входной строке <tex> x </tex> возращает <tex>1</tex> за время <tex> T(m, x) \le t </tex>.
<tex> \mathrm{BH_{1N}} = \lbrace \langle m, x, 1^t \rangle \bigm| m </tex> {{---}} недетерминированная машина Тьюринга, <tex> m(x) = 1, T(m,x) \le t \rbrace </tex>
{{Теорема
|statement=<tex> \mathrm{BH_{1N}} \in \mathrm{NPC} </tex>
}}
== Класс coNP ==
Оракул — абстракция, вычисляющая за <tex>O(1)</tex> времени, верно ли, что <tex>x</tex> принадлежит множеству <tex>A</tex>.
}}
Сложностный класс задач, решаемых алгоритмом из класса <tex>\mathrm{C}</tex> с оракулом для языка <tex>\mathrm{A}</tex>, обозначают <tex>\mathrm{C^A}</tex>.Если <tex>\mathrm{A}</tex> — множество языков, то <tex>\mathrm{C^A} =\bigcup\limits_{D \in A}\mathrm{C^D}</tex>.
== Класс PS ==
<tex>\mathrm{PS}=\bigcup\limits_{p(n) \in poly} \mathrm{DSPACE}(p(n))</tex>.
}}
== PS-полная задача ==
== Класс L ==
== NL-полная задача ==
== Класс P/poly ==
{{Определение
|definition=
= Доказательства =
== Теорема о двух эквивалентных определениях NP (NP = Sigma1) ==
{{Теорема
|statement=
<tex>\mathrm{\Sigma_1}=\mathrm{NP}</tex>.
|proof=
*<tex>\mathrm{\Sigma_1} \subset \mathrm{NP}</tex>.
Пусть <tex>L \in \mathrm{\Sigma_1}</tex>. Тогда существуют <tex>R(x,y)</tex> и полином <tex>p</tex> из определения <tex>\mathrm{\Sigma_1}</tex>. Построим недетерминированную программу <tex>q(x)</tex>, разрешающую <tex>L</tex>.
q(x):
y ←? <tex>\{0,1\}^{p(|x|)}</tex>
return R(x,y)
Если <tex>x\in L</tex>, то программа сможет «угадать» подходящий сертификат. Если <tex>x\notin L</tex>, то подходящего сертификата не существует по определению. Таким образом, <tex>q</tex> разрешает <tex>L</tex>, следовательно <tex>L\in \mathrm{NP}</tex>.
*<tex>\mathrm{NP} \subset \mathrm{\Sigma_1}</tex>.
Пусть <tex>L\in \mathrm{NP}</tex>. Тогда существует недетерминированная программа <tex>q(x)</tex>, разрешающая этот язык. Построим верификатор <tex>R(x,y)</tex>. В качестве сертификата будем использовать последовательность выборов в программе <tex>q</tex>, приводящую к допуску слова (такой сертификат имеет полиномиальную длину, поскольку выборов в <tex>q</tex> может быть сделано не более, чем время ее работы, то есть не более, чем полином). Верификатор будет аналогичен программе <tex>q</tex>, только вместо каждого недетерминированного выбора он будет присваивать значение, указанное в сертификате. Если <tex>x\in L</tex>, то в <tex>q</tex> существует последовательность выборов таких, что <tex>q(x)=1</tex>, следовательно существует и верный сертификат. Если <tex>x\notin L</tex>, то для любой последовательности выборов <tex>q(x)=0</tex>, следовательно подходящего сертификата не существует. Таким образом, <tex>L \in \mathrm{\Sigma_1}</tex>.
}}
== Задача из NPC решается за полином => P = NP ==
Я этого не могу найти, но, казалось бы, это очевидно. Поэтому — отсебятина:
Любая задача из NP сводима по Карпу к любой задаче из NPC, поэтому, если задача из NPC решается за полином, то после сведения мы сможем решить за полином и любую задачу из NP.
== Соотношение между P, NP, PS ==
Очевидно, что <tex>\mathrm{P} \subseteq \mathrm{NP}</tex>, так как детерминированные программы можно рассматривать как недетерминированные, в которых не используется недетерминированный выбор. Вопрос о равенстве данных классов до сих пор остается открытым.
{{Теорема
|statement =
<tex>\mathrm{P} \subseteq \mathrm{PS}</tex>.
|proof = Рассмотрим любой язык <tex>L</tex> из <tex>\mathrm{P}</tex>. Так как <tex>L \in \mathrm{P}</tex>, то существует машина Тьюринга <tex>m</tex>, распознающая <tex>L</tex> за полиномиальное время. Это значит, что <tex>m</tex> не сможет использовать более, чем полиномиальное количество памяти, следовательно <tex> L \in \mathrm{PS}</tex>.
}}
{{Теорема
|statement =
<tex>\mathrm{NP} \subseteq \mathrm{PS}</tex>.
|proof = Рассмотрим любой язык <tex>L</tex> из <tex>\mathrm{NP}</tex>. Так как <tex>L \in \mathrm{NP}</tex>, то существует программа-верификатор <tex>R(x,y)</tex>, что для каждого слова из <tex>L</tex> (и только для них) существует такой сертификат <tex>y</tex> полиномиальной длины, что <tex>R</tex> допускает слово и сертификат. Тогда, чтобы проверить принадлежность слова языку, мы можем перебрать все сертификаты полиномиальной длины. Для этого необходим полиномиальный размер памяти. Из этого следует, что <tex>L \in \mathrm{PS}</tex>.
}}
== Соотношение между L, NL, P ==
{{ Теорема
| statement = <tex>\mathrm{L} \subseteq \mathrm{NL}</tex>
| proof = Детерминированная машина Тьюринга есть частный случай недетерминированной, поэтому <tex>\mathrm{L} \subseteq \mathrm{NL}</tex>.
}}
{{ Теорема
| statement = <tex>\mathrm{NL} \subseteq \mathrm{P}</tex> (следствие из предыдущей теоремы).
| proof = Необходимо доказать, что <tex>\forall \mathrm{B} \in \mathrm{NL}</tex> верно, что <tex>\mathrm{B} \in \mathrm{P}</tex>.
По определению <tex>\mathrm{A} \in \mathrm{NLC} \Leftrightarrow \mathrm{A} \in \mathrm{NL} </tex> и <tex>\forall \mathrm{B} \in \mathrm{NL} </tex> верно, что <tex>\mathrm{B} \leq_{\widetilde{L}} \mathrm{A}</tex>. Следовательно, если <tex>\exists \mathrm{A} \in \mathrm{NLC} : \mathrm{A} \in \mathrm{P}</tex>, то <tex>\forall \mathrm{B}</tex>, сводимого к <tex>\mathrm{A}</tex> верно, что <tex>\mathrm{B} \leq_{\widetilde{P}} \mathrm{A}</tex>, следовательно, поскольку класс <tex>\mathrm{P}</tex> замкнут относительно <tex>\widetilde{\mathrm{P}}</tex>-сведения по Карпу, <tex>\mathrm{B} \in \mathrm{P}</tex>. Таким образом, если существует язык, принадлежащий <tex>\mathrm{NLC}</tex> и <tex>\mathrm{P}</tex>, то теорема доказана. Как было показано выше, <tex>\mathrm{CONN} \in \mathrm{NLC}</tex>. <tex>\mathrm{CONN} \in \mathrm{P}</tex>, что очевидно следует из существования алгоритма DFS.
}}
== Соотношение между ZPP, RP, BPP (вроде то, что нужно) ==
{{Теорема
|statement = <tex>\mathrm{P} \subset \mathrm{ZPP} = \mathrm{RP} \cap \mathrm{coRP}</tex>.
|proof =
Утверждение <tex>\mathrm{P} \subset \mathrm{ZPP}</tex> является очевидным, так как программы, удовлетворяющие ограничениям <tex>\mathrm{P}</tex>, также удовлетворяют ограничениям класса <tex>\mathrm{ZPP}</tex>.
Докажем, что <tex>\mathrm{ZPP} = \mathrm{RP} \cap \mathrm{coRP}</tex>.
Для этого, покажем, что <tex>\mathrm{ZPP}_1 = \mathrm{RP} \cap \mathrm{coRP}</tex>. Тогда из <tex>\mathrm{ZPP} = \mathrm{ZPP}_1</tex> будет следовать требуемое.
1) <tex>\mathrm{ZPP}_1 \subset \mathrm{RP}</tex>. Достаточно вместо <tex>?</tex> возвращать <tex>0</tex>.
2) <tex>\mathrm{ZPP}_1 \subset\mathrm{coRP}</tex>. Достаточно вместо <tex>?</tex> возвращать <tex>1</tex>.
3) <tex>\mathrm{ZPP}_1 \supset \mathrm{RP} \cap \mathrm{coRP}</tex>.
Пусть программа <tex>p_1</tex> удовлетворяет ограничениям <tex>\mathrm{RP}</tex> и ошибается на словах из языка <tex>L</tex> с вероятностью не более <tex>1/2</tex>, а программа <tex>p_2</tex> удовлетворяет ограничениям <tex>\mathrm{coRP}</tex> и ошибается на словах не из языка <tex>L</tex> с аналогичной вероятностью. Построим программу <tex>q</tex> для <tex>\mathrm{ZPP}_1</tex>:
<tex>q</tex>(x)
'''if''' <tex>p_2</tex>(x) = 0
'''return''' 0
'''if''' <tex>p_1</tex>(x) = 1
'''return''' 1
'''return''' ?
Вероятность вывести <tex>?</tex> есть <tex>\operatorname{P}(p_2(x) = 1, p_1(x) = 0) \le 1/2</tex>.
}}
{{Теорема
|statement =
<tex>\mathrm{RP} \cup \mathrm{coRP} \subset \mathrm{BPP}</tex>.
|proof =
Пусть <tex>p</tex> — программа для <tex>L \in \mathrm{RP}</tex>. Программу <tex>q</tex> для <tex>\mathrm{BPP}</tex> определим следующим образом:
<tex>q</tex>(x)
u <- <tex>p</tex>(x)
v <- <tex>p</tex>(x)
'''return''' u '''or''' v
Пусть <tex>x \in L</tex>. В этом случае вероятность ошибки равна <tex>\operatorname{P}(u = 0, v = 0) = \operatorname{P}(u = 0) \cdot \operatorname{P}(v = 0) \le 1/4</tex>.
Пусть <tex>x \notin L</tex>. Тогда с вероятностью <tex>1</tex> будет верно <tex>u = 0, v = 0</tex> и <tex>q</tex> вернет правильный ответ.
Аналогично доказывается, что <tex>\mathrm{coRP} \subset \mathrm{BPP}</tex>.
}}
== BPP входит в PS ==
<tex>BPP \subset PP</tex> (так как <tex>\forall p \forall x P(p(x) = [x \in L]) \geq \frac 2 3 \Rightarrow P(p(x) = [x \in L]) > \frac 1 2</tex>).
Пусть <tex>p</tex> — программа для языка <tex>L \in \mathrm{PP}</tex>. Она используют не более чем полиномиальное количество вероятностных бит, так как сама работает за полиномиальное время. Тогда программа для <tex>\mathrm{PS}</tex> будет перебирать все участки вероятностных лент нужной полиномиальной длины и запускать на них <tex>p</tex>. Ответом будет <tex>0</tex> или <tex>1</tex> в зависимости от того, каких ответов <tex>p</tex> оказалось больше.
== Интерактивное доказательство для GNI ==
{{Теорема
|statement=<tex>\mathrm{GNI} \in \mathrm{IP}[1]</tex>.
|proof=
Будем использовать следующий алгоритм для <tex>\mathit{Verifier}</tex>:
# Возьмём случайное число <tex>i \in \{0, 1\}</tex> и случайную перестановку <tex>\pi</tex> с вероятностной ленты; <br/>
# Создадим новый граф, перемешав вершины графа c номером <tex>i</tex> перестановкой <tex>\pi</tex>; <br/>
# Перешлём <tex>\mathit{Prover}</tex> полученный граф с просьбой определить, из какого из исходных графов он был получен; <br/>
# Получив ответ, сравним его с правильным ответом — числом <tex>i</tex>; <br/>
# Если полученный ответ не совпадёт с <tex>i</tex>, то вернём <tex>0</tex>; <br/>
# Иначе повторим первые пять шагов ещё раз и перейдём к последнему шагу; <br/>
# Если мы ещё не вернули <tex>0</tex>, то вернём <tex>1</tex>.
Покажем, что это удовлетворяет ограничениям на <tex>\mathrm{IP}[1]</tex>.
Во-первых, очевидно, что число раундов не превосходит двух. <br/>
Рассмотрим теперь случаи
* <tex> \langle G, H \rangle \in \mathrm{GNI}</tex>. Тогда <tex>G</tex> и <tex>H</tex> неизоморфны и <tex>\mathit{Prover}</tex> сможет определить какой граф был перемешан <tex>\mathit{Verifier}</tex>. Таким образом, <tex>\mathit{Prover}</tex> сможет два раза подряд вернуть правильный ответ и в итоге <tex>\mathit{Verifier}</tex> вернёт 1.
* <tex> \langle G, H \rangle \notin \mathrm{GNI}</tex>. Тогда <tex>G</tex> и <tex>H</tex> изоморфны и <tex>\mathit{Prover}</tex> не сможет определить какой граф был перемешан <tex>\mathit{Verifier}</tex>. Так как <tex>\mathit{Prover}</tex> заинтересован в том, чтобы <tex>\mathit{Verifier}</tex> принял слово, ему необходимо угадать правильный ответ (иначе <tex>\mathit{Verifier}</tex> просто вернёт <tex>0</tex>). Вероятность того, что <tex>\mathit{Verifier}</tex> примет слово <tex>x</tex>, когда оно не принадлежит языку (то есть <tex>\mathit{Prover}</tex> два раза подряд верно угадает номер графа), равна <tex>\frac{1}{4}</tex>.
Таким образом, построенный протокол удовлетворяет условию теоремы.
}}
= Формулировки =
== Теорема Кука ==
<tex> \mathrm{SAT}</tex> {{---}} язык булевых формул из <tex> n </tex> переменных, для которых существует подстановка, при которой формула истинна.
<tex> \mathrm{SAT} = \lbrace \varphi \mid \exists x : \varphi(x) = 1 \rbrace </tex>
{{Теорема
|author=Кук
|statement=<tex> \mathrm{SAT}\in \mathrm{NPC} </tex>
}}
== Теорема Ладнера ==
{{Теорема
|author=Ладнер
|statement=
<tex>\mathrm{P} \neq \mathrm{NP} \Rightarrow \mathrm{NP} \setminus (\mathrm{P} \cup \mathrm{NPC}) \neq \varnothing</tex>.
}}
== Теорема Бейкера-Гилла-Соловея (не существует релятивизующегося доказательства P != NP) ==
{{ Теорема
|statement = Существуют такие оракулы <tex>A</tex> и <tex>B</tex>, что <tex>\mathrm{P^A} = \mathrm{NP^A} </tex> и <tex>\mathrm{P^B} \ne \mathrm{NP^B} </tex>.
}}
{{ Утверждение
| statement = Если существует решение вопроса равенства <tex>\mathrm{P}</tex> и <tex> \mathrm{NP}</tex>, то оно не должно «релятивизоваться».
}}
== Теорема Мэхени (нет редких NP-полных языков) ==
{{Определение
|definition=
<tex>\mathrm{SPARSE} = \{L \bigm{|} \exists</tex> полином <tex>p: \forall n \, |L \cap \Sigma^n| \le p(n)\}</tex>.
}}
{{Теорема
|author=Махэни
|statement=
<tex>\mathrm{NPC} \cap \mathrm{SPARSE} \ne \varnothing \Rightarrow \mathrm{P}=\mathrm{NP}</tex>.
}}
== Теорема Левина (об оптимальной NP-программе) ==
{{Теорема
|author=Левин
|statement=
Для любого языка <tex>L \in \Sigma_1</tex> и соответствующего ему (из определения <tex>\Sigma_1</tex>) отношения <tex>R</tex> существует «оптимальная» (работающая «не сильно дольше», чем любая другая) программа <tex>p</tex>, сопоставляющая словам из <tex>L</tex> их сертификаты, то есть:
# <tex>x \in L \Leftrightarrow R(x, p(x)) = 1</tex>;
# для любой другой программы <tex>q</tex>, для которой верно <tex>x \in L \Leftrightarrow R(x, q(x)) = 1</tex>, найдутся такие константа <tex>c</tex> и полином <tex>r</tex>, что для любого <tex>x</tex> выполняется: <tex>T(p, x) \le c \cdot T(q, x) + r(|x|)</tex>.
}}
== Теорема Сэвича (PS = NPS) ==
{{Теорема
|statement =
Для любой <tex>f(n) \ge \log n </tex> справедливо: <tex>\mathrm{NSPACE}(f(n)) \subseteq \mathrm{DSPACE}(f(n)^2)</tex>. <br>
То есть, если недетерминированная машина Тьюринга может решить проблему, используя <tex>f(n)</tex> памяти, то существует детерминированная машина Тьюринга, которая решает эту же проблему, используя не больше, чем <tex>f(n)^2</tex> памяти.
}}
== TQBF - PS-полная задача ==
{{Определение
|definition=<tex>\mathrm{TQBF}</tex> расшифровывается как '''True Quantified Boolean Formula'''. Это язык верных булевых формул с кванторами.<br/>
<tex>\mathrm{TQBF}=\{Q_1 x_1 Q_2 x_2 \ldots Q_n x_n \phi(x_1, x_2, \dots, x_n), Q_i \in \{\forall, \exists\}\}</tex>.
}}
{{Определение
|definition=<tex>Quantified Boolean Formula</tex> — это пропозициональная формула с кванторами. Кванторы для каждой переменной записываются в начале выражения.
}}
{{Теорема
|statement=<tex>\mathrm{TQBF} \in \mathrm{PSC}</tex>.
}}
== Теорема Иммермана (NL = coNL) ==
{{ Теорема
|statement = <tex>\mathrm{coNL} = \mathrm{NL}.</tex>
}}
== Теоремы о полиномиальной иерархии ==
{{Теорема
|statement = Если существует <tex>i \colon \Sigma_i = \Sigma_{i+1}</tex>, то <tex>\Sigma_i = \mathrm{PH}</tex>.
}}
{{Теорема
|statement = Если существует <tex>i > 0\colon \Sigma_i = \Pi_i</tex>, то <tex>\Sigma_i = \mathrm{PH}</tex>.
}}
== Теорема Лаутемана (BPP и полиномиальная иерархия) ==
{{ Теорема
|about = Лаутеман
|statement = <tex>\mathrm{BPP} \subset \mathrm{\Sigma_2} \cap \mathrm{\Pi_2}</tex>
}}
== Теорема Шамира и др. (IP = PS) ==
{{Теорема
|author=Шамир
|statement=<tex>\mathrm{IP} = \mathrm{PS}</tex>
}}
== PCP-теорема ==
{{Теорема
|id=pcp_th
|about=<tex>\mathrm{PCP}</tex> теорема
|statement=<tex>\mathrm{PCP}[\log n, O(1)] = \mathrm{NP}</tex>
}}
