WikiSysop: 1 версия

2008-08-04T09:55:51Z

1 версия

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

Класс сложности [[ZPP]] (''Zero-Probability Polynomial-time'') можно определить, как пересечение классов [[RP]] и [[coRP]]:

<amsmath>
{\cal ZPP}={\cal RP} \cap co{\cal RP}
</amsmath>

или, через самостоятельное определение:

Класс сложности [[ZPP]] состоит из всех языков ''L''
для которых существует полиномиальная [[вероятностная машина Тьюринга]] ''M'', возвращающая только ответы «0», «1», «не знаю», причем::

<amsmath>
\begin{split}
x \in L &\Rightarrow P[M(x)=1] > \frac{1}{2}
\hspace{3em}
P[M(x)=1]+P[M(x)=\mbox{<<не знаю>>}]=1
\\
x \notin L &\Rightarrow P[M(x)=0] > \frac{1}{2}
\hspace{3em}
P[M(x)=0]+P[M(x)=\mbox{<<не знаю>>}]=1
\end{split}
</amsmath>

<h4>Диаграмма «ближайших» классов</h4>

<graph>
digraph G{
P [URL="P"];
NP [URL="NP"];
coNP [URL="coNP"];
ZPP [URL="ZPP",style="filled",fillcolor="green"];
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}}

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

WikiSysop: 1 версия