Класс co-NP

Материал из Викиконспекты
Версия от 18:06, 2 июня 2010; Ulyantsev (обсуждение | вклад) (переименовал «Класс coNP» в «Класс co-NP»: Дефис не помешает)
(разн.) ← Предыдущая | Текущая версия (разн.) | Следующая → (разн.)
Перейти к: навигация, поиск

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

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

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

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

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

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