Просмотр исходного текста страницы BPP

Класс сложности '''BPP''' (''Bounded-Probability Polynomial-time'') состоит из всех языков ''L'' для которых существует полиномиальная [[вероятностная машина Тьюринга]] ''M'', такая что:

<amsmath>
\begin{split}
 x \in L &\Rightarrow P[M(x)=1]\geq \frac{2}{3} \\
 x \notin L &\Rightarrow P[M(x)=0]\geq \frac{2}{3} \\
\end{split}
</amsmath>

Можно показать, что будут эквивалентны также следующие определения класса [[BPP]]:

=== «Строгое» определение ===
Класс сложности [[BPP]] состоит из всех языков ''L'' для которых существует полиномиальная [[вероятностная машина Тьюринга]] ''M'', и полином ''p(*)'', такие что:

<amsmath>
\begin{split}
 x \in L &\Rightarrow P[M(x)=1]\geq 1 - 2^{-p(|x|)} \\
 x \notin L &\Rightarrow P[M(x)=0]\geq 1 - 2^{-p(|x|)} \\
\end{split}
</amsmath>

=== «Свободное» определение ===
Класс сложности [[BPP]] состоит из всех языков ''L'' для которых существует 
* полиномиально вычислимая функция <amsmath>f:N\mapsto [0,1]</amsmath>,
* полиномиальная [[вероятностная машина Тьюринга]] ''M'', 
* полином ''p(*)'', 
такие что:

<amsmath>
\begin{split}
 x \in L    &\Rightarrow P[M(x)=1]\geq f(|x|) + \frac{1}{p(|x|)} \\
 x \notin L &\Rightarrow P[M(x)=1]< f(|x|) - \frac{1}{p(|x|)} \\
\end{split}
</amsmath>

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

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