Класс co-NP
В теории сложности класс co-NP — класс языков (задач), дополнение к которым лежит в NP.
co-NP = (См. Полиномиальная иерархия)
Теоремы, связанные с coNP
Если NP ≠ co-NP, тогда P ≠ NP.
Пример задач класса coNP
- Язык тавтологий — задача определения, является ли булева формула тавтологией. TAUT
