Класс co-NP — различия между версиями
(определение, одна теорема. один пример) |
|||
| Строка 2: | Строка 2: | ||
==Теоремы, связанные с coNP== | ==Теоремы, связанные с coNP== | ||
| − | Если <tex>NP | + | Если <tex>NP \ne coNP</tex>, тогда <tex>P \neq NP</tex> |
==Пример задач класса coNP== | ==Пример задач класса coNP== | ||
* Язык тавтологий, задача определения, является ли булева формула тавтологией. TAUT | * Язык тавтологий, задача определения, является ли булева формула тавтологией. TAUT | ||
Версия 16:57, 18 марта 2010
В теории сложности Класс coNP - класс языков (задач), дополнение к которым является NP.
Теоремы, связанные с coNP
Если , тогда
Пример задач класса coNP
- Язык тавтологий, задача определения, является ли булева формула тавтологией. TAUT
