1632
правки
Изменения
м
rollbackEdits.php mass rollback
В теории сложности '''Класскласс co-NP''' <tex>coNP</tex> — класс языков (задач), дополнение к которым является лежит в '''[[NP]]'''. '''co-NP''' = <tex>\Pi_1</tex> (См.[[Полиномиальная иерархия]])
==Теоремы, связанные с coNP==
Если <tex>'''NP \''' &ne coNP</tex>; '''co-NP''', тогда <tex>'''[[P \neq ]]''' ≠ '''NP</tex>'''.
==Пример задач класса coNP==
* Язык тавтологий, — задача определения, является ли булева формула тавтологией. TAUT