Класс co-NP — различия между версиями
| Строка 1: | Строка 1: | ||
В теории сложности '''Класс''' <tex>coNP</tex> — класс языков (задач), дополнение к которым является NP. | В теории сложности '''Класс''' <tex>coNP</tex> — класс языков (задач), дополнение к которым является NP. | ||
| + | |||
| + | <tex>coNP = \Pi_1</tex> (См. [[Полиномиальная иерархия]]) | ||
==Теоремы, связанные с 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
