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