315
правок
Изменения
Нет описания правки
= Формулировки =
== Теорема Кука ==
<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>.
}}
== Теорема Мэхени (нет редких 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>
}}
