130
правок
Изменения
Переименовал co-NP в coNP
То есть <tex>\mathrm{NP}</tex> — это множество языков, разрешимых недетерминированной программой за полиномиальное время.
{{Определение
|definition=<tex>\textrmmathrm{co-NPcoNP} = \{L \bigm| \overline{L} \in \mathrm{NP}\}</tex>.
}}
То есть <tex>\textrmmathrm{co-NPcoNP}</tex> — это множество языков, дополнение к которым лежит в NP.
{{Определение
|definition=<tex>\mathrm{\Sigma_1}=\{L\bigm|\exists R(x,y)\in \tilde{\mathrm{P}}, p(n) \in poly : x\in L\Leftrightarrow\exists y : |y|\le p(|x|), R(x,y)=1\}</tex>.
Все эти языки также являются [[Примеры_NP-полных_языков._Теорема_Кука|<tex>\mathrm{NP}</tex>-полными]]. По [[Теорема Ладнера|теореме Ладнера]], существует язык из <tex>\mathrm{NP}</tex>, не являющийся <tex>\mathrm{NP}</tex>-полным.
== Примеры языков из co-NP coNP ==
* Даны <tex>n</tex> целых чисел. Верно ли, что любое их непустое подмножество имеет ненулевую сумму?
* TAUT: определить, является ли заданная булева формула тавтологией. К этой задаче тривиально сводится дополнение к SAT: если отрицание формулы невыполнимо, то она является тавтологией, и наоборот.
