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|\)

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

Graph image creation requires permission to upload.


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