315
правок
Изменения
Нет описания правки
}}
== Видимо, это про 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>
== NP-полнота <tex> \mathrm{BH_{1N}} </tex> ==
{{Теорема
|statement=<tex> \mathrm{BH_{1N}} \in \mathrm{NPC} </tex>
}}
== Класс coNP ==
