Класс co-NP — различия между версиями
Ulyantsev (обсуждение | вклад) |
|||
| Строка 1: | Строка 1: | ||
| − | В теории сложности ''' | + | В теории сложности '''класс co-NP''' — класс языков (задач), дополнение к которым лежит в '''[[NP]]'''. |
| − | <tex> | + | '''co-NP''' = <tex>\Pi_1</tex> (См. [[Полиномиальная иерархия]]) |
==Теоремы, связанные с coNP== | ==Теоремы, связанные с coNP== | ||
| − | Если | + | Если '''NP''' ≠ '''co-NP''', тогда '''[[P]]''' ≠ '''NP'''. |
==Пример задач класса coNP== | ==Пример задач класса coNP== | ||
| − | * Язык тавтологий | + | * Язык тавтологий — задача определения, является ли булева формула тавтологией. TAUT |
Версия 18:05, 2 июня 2010
В теории сложности класс co-NP — класс языков (задач), дополнение к которым лежит в NP.
co-NP = (См. Полиномиальная иерархия)
Теоремы, связанные с coNP
Если NP ≠ co-NP, тогда P ≠ NP.
Пример задач класса coNP
- Язык тавтологий — задача определения, является ли булева формула тавтологией. TAUT
