Класс co-NP — различия между версиями

Материал из Викиконспекты
Перейти к: навигация, поиск
(определение, одна теорема. один пример)
 
м (rollbackEdits.php mass rollback)
 
(не показано 7 промежуточных версий 4 участников)
Строка 1: Строка 1:
В теории сложности '''Класс coNP''' - класс языков (задач), дополнение к которым является NP.
+
В теории сложности '''класс co-NP''' — класс языков (задач), дополнение к которым лежит в '''[[NP]]'''.
 +
 
 +
'''co-NP''' = <tex>\Pi_1</tex> (См. [[Полиномиальная иерархия]])
  
 
==Теоремы, связанные с coNP==
 
==Теоремы, связанные с coNP==
Если <tex>NP = coNP</tex>, тогда <tex>P \neq NP</tex>
+
Если '''NP''' &ne; '''co-NP''', тогда '''[[P]]''' &ne; '''NP'''.
  
 
==Пример задач класса coNP==
 
==Пример задач класса coNP==
* Язык тавтологий, задача определения, является ли булева формула тавтологией. TAUT
+
* Язык тавтологий &mdash; задача определения, является ли булева формула тавтологией. TAUT

Текущая версия на 19:30, 4 сентября 2022

В теории сложности класс co-NP — класс языков (задач), дополнение к которым лежит в NP.

co-NP = [math]\Pi_1[/math] (См. Полиномиальная иерархия)

Теоремы, связанные с coNP

Если NPco-NP, тогда PNP.

Пример задач класса coNP

  • Язык тавтологий — задача определения, является ли булева формула тавтологией. TAUT