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

Материал из Викиконспекты
Перейти к: навигация, поиск
Строка 5: Строка 5:
 
==Теоремы, связанные с coNP==
 
==Теоремы, связанные с coNP==
 
Если <tex>NP \ne coNP</tex>, тогда <tex>P \neq NP</tex>
 
Если <tex>NP \ne coNP</tex>, тогда <tex>P \neq NP</tex>
 
  
 
==Пример задач класса coNP==
 
==Пример задач класса coNP==
 
* Язык тавтологий, задача определения, является ли булева формула тавтологией. TAUT
 
* Язык тавтологий, задача определения, является ли булева формула тавтологией. TAUT

Версия 18:51, 18 марта 2010

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

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

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

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

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

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