|
|
(не показана 1 промежуточная версия 1 участника) |
Строка 1: |
Строка 1: |
− | Класс сложности '''BPP''' (''Bounded-Probability Polynomial-time'') состоит из всех языков ''L'' для которых существует полиномиальная [[вероятностная машина Тьюринга]] ''M'', такая что:
| + | #REDIRECT [[discopal:BPP]] |
− | | + | |
− | <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}}
| + | |