Персональные инструменты
 

ZPP — различия между версиями

Материал из CustisWiki

Перейти к: навигация, поиск
м (реплицировано из внутренней CustisWiki)
 
м (Содержимое страницы заменено на «#REDIRECT [[discopal:{{PAGENAME}}]]»)
 
(не показана 1 промежуточная версия 1 участника)
Строка 1: Строка 1:
Класс сложности [[ZPP]] (''Zero-Probability Polynomial-time'') можно определить, как пересечение классов [[RP]] и [[coRP]]:
+
#REDIRECT [[discopal:{{PAGENAME}}]]
 
+
<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}}
+

Текущая версия на 20:38, 13 июня 2011

  1. REDIRECT discopal:ZPP