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