Класс co-NP

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

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

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

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

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

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

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