Класс co-NP

В теории сложности класс co-NP — класс языков (задач), дополнение к которым лежит в NP.

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

Теоремы, связанные с coNP

Если NP ≠ co-NP, тогда P ≠ NP.

Пример задач класса coNP

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