Изменения
→Теорема о двух эквивалентных определениях NP (NP = Sigma1)
<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>
Оракул — абстракция, вычисляющая за <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-полная задача ==
== Класс P/poly ==
{{Определение
|definition=
Пусть <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{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>
}}
