CoNP

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

$co{\cal NP} \equiv \{L|\overline{L} \in {\cal NP}\}$

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

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

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

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

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