83
правки
Изменения
определение, одна теорема. один пример
В теории сложности '''Класс coNP''' - класс языков (задач), дополнение к которым является NP.
==Теоремы, связанные с coNP==
Если <tex>NP = coNP</tex>, тогда <tex>P \neq NP</tex>
==Пример задач класса coNP==
* Язык тавтологий, задача определения, является ли булева формула тавтологией. TAUT
==Теоремы, связанные с coNP==
Если <tex>NP = coNP</tex>, тогда <tex>P \neq NP</tex>
==Пример задач класса coNP==
* Язык тавтологий, задача определения, является ли булева формула тавтологией. TAUT
