Класс co-NP

Материал из Викиконспекты
(перенаправлено с «Класс coNP»)
Перейти к: навигация, поиск

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

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

Теоремы, связанные с coNP[править]

Если NPco-NP, тогда PNP.

Пример задач класса coNP[править]

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