Класс co-NP

В теории сложности Класс [math]coNP[/math] — класс языков (задач), дополнение к которым является NP.

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

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

Если [math]NP \ne coNP[/math], тогда [math]P \neq NP[/math]

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

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