Изменения

В теории сложности '''Класскласс co-NP''' <tex>coNP</tex> &mdash; класс языков (задач), дополнение к которым является лежит в '''[[NP]]'''.

'''co-NP''' = <tex>coNP = \Pi_1</tex> (См. [[Полиномиальная иерархия]])

Если <tex>'''NP \''' &ne coNP</tex>; '''co-NP''', тогда <tex>'''[[P \neq ]]''' &ne; '''NP</tex>'''.

* Язык тавтологий, &mdash; задача определения, является ли булева формула тавтологией. TAUT