CoNP — класс-дополнение к классу NP.

c o N P { L | L N P } co{\cal NP} \equiv \{L|\overline{L} \in {\cal NP}\}

Определение через детерминированную машину ТьюрингаПравить

Язык L Σ L \subseteq \Sigma^* принадлежит классу coNP, если существует детерминированная машина Тьюринга M и некоторый полином p(*) такие, что

L = { x Σ :     y ,   | y | L=\{ x \in \Sigma^* : \ \forall \ y, \ |y|

Диаграмма «ближайших» классов сложностиПравить

G P P ZPP ZPP P->ZPP in NP NP PP PP NP->PP in coNP coNP coNP->PP in BPP BPP ZPP->BPP in RP RP ZPP->RP in coRP coRP ZPP->coRP in BPP->PP in RP->NP in RP->BPP in coRP->coNP in coRP->BPP in


По крайней мере часть этого текста взята с ресурса http://lib.custis.ru/ под лицензией GDFL.Список авторов доступен на этом ресурсе в статье под тем же названием.