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

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

Материал из CustisWiki

Перейти к: навигация, поиск
м (реплицировано из внутренней CustisWiki)
 
м (Содержимое страницы заменено на «#REDIRECT [[discopal:{{PAGENAME}}]]»)
 
(не показана 1 промежуточная версия 1 участника)
Строка 1: Строка 1:
Класс сложности [[PP]] (''Probability Polynomial-time'') состоит из всех языков ''L''
+
#REDIRECT [[discopal:{{PAGENAME}}]]
для которых существует полиномиальная [[вероятностная машина Тьюринга]] ''M'', такая что:
+
 
+
<amsmath>
+
\begin{split}
+
x \in L &\Rightarrow P[M(x)=1]    > \frac{1}{2} \\
+
x \notin L &\Rightarrow P[M(x)=0] > \frac{1}{2} \\
+
\end{split}
+
</amsmath>
+
 
+
<br/>
+
 
+
Можно показать, что класс [[PP]], можно определить с «чуть пониженными» требованиями к распознающей
+
[[вероятностная машина Тьюринга|ВМТ]] ''M'':
+
 
+
<amsmath>
+
\begin{split}
+
x \in L &\Rightarrow P[M(x)=1]    \geq \frac{1}{2} \\
+
x \notin L &\Rightarrow P[M(x)=0] > \frac{1}{2} \\
+
\end{split}
+
</amsmath>
+
 
+
или
+
 
+
<amsmath>
+
\begin{split}
+
x \in L &\Rightarrow P[M(x)=1]    > \frac{1}{2} \\
+
x \notin L &\Rightarrow P[M(x)=0] \geq  \frac{1}{2} \\
+
\end{split}
+
</amsmath>
+
 
+
<h4>Диаграмма «ближайших» классов сложности</h4>
+
<graph>
+
digraph G{
+
  NP  [URL="NP"];
+
  coNP [URL="coNP"];
+
  ZPP [URL="ZPP"];
+
  BPP [URL="BPP"];
+
  PP  [URL="PP",style="filled",fillcolor="green"];
+
  RP [URL="RP"];
+
  PSPACE [URL="PSPACE"];
+
  coRP [URL="coRP"];
+
  NEXP [URL="NEXP"];
+
 
+
  rankdir=LR; ranksep=0.3;
+
  edge[arrowtail="none",arrowhead="crow",label=" in",fontsize=8,fontcolor="blue"];
+
 
+
  ZPP->RP;
+
  ZPP->coRP;
+
 
+
  ZPP->BPP;
+
 
+
  coRP->BPP;
+
  RP->BPP;
+
 
+
  coRP->coNP;
+
  RP->NP;
+
 
+
  BPP->PP;
+
 
+
  coNP->PP;
+
  NP->PP;
+
 
+
  PP->NEXP;
+
  PP->PSPACE;
+
}
+
</graph>
+
 
+
 
+
[[Category:Классы сложности]]
+
{{replicate-from-custiswiki-to-lib}}
+

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

  1. REDIRECT discopal:PP