|
|
| Строка 1: |
Строка 1: |
| − | Класс сложности '''RP''' (''Random Polynomial-time'') состоит из всех языков ''L'' для которых существует полиномиальная [[вероятностная машина Тьюринга]] ''M'', такая что:
| + | #REDIRECT [[discopal:{{PAGENAME}}]] |
| − | | + | |
| − | <amsmath>
| + | |
| − | \begin{split}
| + | |
| − | x \in L &\Rightarrow P[M(x)=1]\geq \frac{1}{2} \\
| + | |
| − | x \notin L &\Rightarrow P[M(x)=0]=1
| + | |
| − | \end{split}
| + | |
| − | </amsmath>
| + | |
| − | | + | |
| − | Можно, пользуясь тем, что в в «offline»-определении [[вероятностная машина Тьюринга|ВМТ]] подразумевается отделенность вероятностных данных от обычной ДМТ, дать альтернативное определение, заменив вероятности, на доли строк-сертификатов:
| + | |
| − | | + | |
| − | ===Определение через Детерминированную Машину Тьюринга===
| + | |
| − | | + | |
| − | Класс сложности '''RP''' состоит из всех языков ''L'' для которых существует некий полином ''p(*)'' и полиномиальная [[машина Тьюринга]] ''M(x,y)'', такая что:
| + | |
| − | | + | |
| − | <amsmath>
| + | |
| − | \begin{split}
| + | |
| − | x \in L &\Rightarrow \frac{|\{y:M(x,y)=1,|y|\leq p(|x|)\}|}{2^{p(|x|)}}\geq \frac{1}{2} \\
| + | |
| − | x \notin L &\Rightarrow \forall y, M(x,y)=0
| + | |
| − | \end{split}
| + | |
| − | </amsmath>
| + | |
| − | | + | |
| − | | + | |
| − | Можно показать, что будут эквивалентны также следующие определения класса [[RP]]:
| + | |
| − | | + | |
| − | === «Строгое» определение ===
| + | |
| − | Класс сложности [[RP]] состоит из всех языков ''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)=1]=0 \\
| + | |
| − | \end{split}
| + | |
| − | </amsmath>
| + | |
| − | | + | |
| − | === «Свободное» определение ===
| + | |
| − | Класс сложности [[RP]] состоит из всех языков ''L'' для которых существует полиномиальная [[вероятностная машина Тьюринга]] ''M'', и полином ''p(*)'', такие что:
| + | |
| − | | + | |
| − | <amsmath>
| + | |
| − | \begin{split}
| + | |
| − | x \in L &\Rightarrow P[M(x)=1]\geq \frac{1}{p(|x|)} \\
| + | |
| − | x \notin L &\Rightarrow P[M(x)=1]=0 \\
| + | |
| − | \end{split}
| + | |
| − | </amsmath>
| + | |
| − | | + | |
| − | Аналогичные определения можно дать и для класса [[coRP]].
| + | |
| − | | + | |
| − | ===Диаграмма «ближайших» классов===
| + | |
| − | | + | |
| − | <graph>
| + | |
| − | digraph G{
| + | |
| − | P [URL="P"];
| + | |
| − | NP [URL="NP"];
| + | |
| − | coNP [URL="coNP"];
| + | |
| − | ZPP [URL="ZPP"];
| + | |
| − | BPP [URL="BPP"];
| + | |
| − | PP [URL="PP"];
| + | |
| − | RP [URL="RP",style="filled",fillcolor="green"];
| + | |
| − | 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}}
| + | |
