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

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

Материал из CustisWiki

Перейти к: навигация, поиск
м (реплицировано из внутренней CustisWiki)
 
м (Содержимое страницы заменено на «#REDIRECT [[discopal:{{PAGENAME}}]]»)
 
(не показана 1 промежуточная версия 1 участника)
Строка 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}}
+

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

  1. REDIRECT discopal:RP