Изменения
Нет описания правки
== NP-полнота <tex> BH_{1N} </tex> ==
<tex> BH_{1N} </tex> {{---}} язык троек <tex> \langle m, x, 1^t \rangle </tex>, таких что недетерминированная машина Тьюринга <tex> m </tex> на входной строке <tex> x </tex> возращает 1 за время <tex> T(m, x) \le t </tex>.
<tex> BH_{1N} = \lbrace \langle m, x, 1^t \rangle | m </tex> {{---}} недерминированная машина Тьюринга, <tex> m(x) = 1, T(m,x) \le t \rbrace </tex>
{{Теорема
|statement=<tex> BH_{1N} \in NPC </tex>
# <tex> BH_{1N} \in NPH </tex>
# <tex> BH_{1N} \in NP </tex>
}}
== NP-полнота <tex> SAT </tex> ==
<tex> SAT </tex> {{---}} язык булевых формул, для которых существует подстановка, при которой формула истинна.
<tex> SAT = \lbrace \varphi\ |\ \exists x : \varphi(x) = 1 \rbrace </tex>
{{Теорема
|author=Кук
|statement=<tex> SAT \in NPC </tex>
|proof=
# <tex> SAT \in NPH </tex>
# <tex> SAT \in NP </tex> <br>Можно написать недетерминированную программу, которая распознает язык SAT. Она будет недетерминированно выбирать подстановку, проверять истинна ли формула при такой подстановке и выдавать ответ.
}}
