CoNP

From Традиция
Jump to navigation Jump to search

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

\(co{\cal NP} \equiv \{L|\overline{L} \in {\cal NP}\}\)

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

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

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

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

<graphviz>digraph G{

 P [URL="P"];
 NP   [URL="NP"];
 coNP [URL="coNP",style="filled",fillcolor="green"];
 ZPP [URL="ZPP"];
 BPP [URL="BPP"];
 PP  [URL="PP"];
 RP [URL="RP"];
 coRP [URL="coRP"];
 
 rankdir=LR; ranksep=0.3;
 edge[arrowtail="none",arrowhead="crow",label=" in",fontsize=8,fontcolor="blue"];
 P -> ZPP;
 
 ZPP->RP;
 ZPP->coRP;
 ZPP->BPP;
 coRP->BPP;
 RP->BPP;
 coRP->coNP;
 RP->NP;
 BPP->PP;
 coNP->PP;
 NP->PP;

}</graphviz>


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