WikiSysop: 1 версия

2008-08-04T09:55:46Z

1 версия

Новая страница

Класс-дополнение к классу [[NP]].

<amsmath>
co{\cal NP} \equiv \{L|\overline{L} \in {\cal NP}\}
</amsmath>

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

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

<amsmath>
L=\{ x \in \Sigma^* : \ \forall \ y, \ |y|<p(|x|)
\ \ M(x,y)=0\}
</amsmath>

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

<graph>
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;
}
</graph>

[[Category:Классы сложности]]
{{replicate-from-custiswiki-to-lib}}

CoNP - История изменений

WikiSysop: 1 версия