Класс co-NP — различия между версиями

Материал из Викиконспекты
Перейти к: навигация, поиск
м (rollbackEdits.php mass rollback)
 
(не показаны 2 промежуточные версии 2 участников)
(нет различий)

Текущая версия на 19:30, 4 сентября 2022

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

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

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

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

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

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