Класс 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
В теории сложности Класс — класс языков (задач), дополнение к которым является NP.
(См. Полиномиальная иерархия)
Теоремы, связанные с coNP
Если , тогда
Пример задач класса coNP
- Язык тавтологий, задача определения, является ли булева формула тавтологией. TAUT
