WikiSysop: 1 версия

2008-08-04T09:55:49Z

1 версия

Новая страница

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

<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}}

RP - История изменений

WikiSysop: 1 версия