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

StasFomin: Содержимое страницы заменено на «#REDIRECT discopal:{{PAGENAME}}»

2011-06-13T17:39:00Z

Содержимое страницы заменено на «#REDIRECT [[discopal:{{PAGENAME}}]]»

WikiSysop: 1 версия

2008-08-04T09:55:49Z

1 версия

BenderBot: реплицировано из внутренней CustisWiki

2005-12-07T04:40:50Z

реплицировано из внутренней CustisWiki

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

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

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

<br/>

Можно показать, что класс [[PP]], можно определить с «чуть пониженными» требованиями к распознающей
[[вероятностная машина Тьюринга|ВМТ]] ''M'':

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

или

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

<h4>Диаграмма «ближайших» классов сложности</h4>
<graph>
digraph G{
NP [URL="NP"];
coNP [URL="coNP"];
ZPP [URL="ZPP"];
BPP [URL="BPP"];
PP [URL="PP",style="filled",fillcolor="green"];
RP [URL="RP"];
PSPACE [URL="PSPACE"];
coRP [URL="coRP"];
NEXP [URL="NEXP"];

rankdir=LR; ranksep=0.3;
edge[arrowtail="none",arrowhead="crow",label=" in",fontsize=8,fontcolor="blue"];

ZPP->RP;
ZPP->coRP;

ZPP->BPP;

coRP->BPP;
RP->BPP;

coRP->coNP;
RP->NP;

BPP->PP;

coNP->PP;
NP->PP;

PP->NEXP;
PP->PSPACE;
}
</graph>

[[Category:Классы сложности]]
{{replicate-from-custiswiki-to-lib}}

StasFomin в 15:06, 6 декабря 2005

2005-12-06T15:06:32Z

← Предыдущая	Версия 09:55, 4 августа 2008
(не показана 1 промежуточная версия 1 участника)
(нет различий)

@@ Строка 1: / Строка 1: @@
-Класс сложности [[PP]] (''Probability Polynomial-time'') состоит из всех языков ''L''
+#REDIRECT [[discopal:{{PAGENAME}}]]
-для которых существует полиномиальная [[вероятностная машина Тьюринга]] ''M'', такая что:
-−
-<amsmath>
-\begin{split}
- x \in L &\Rightarrow P[M(x)=1]    > \frac{1}{2} \\
- x \notin L &\Rightarrow P[M(x)=0] > \frac{1}{2} \\
-\end{split}
-</amsmath>
-−
-<br/>
-−
-Можно показать, что класс [[PP]], можно определить с «чуть пониженными» требованиями к распознающей
-[[вероятностная машина Тьюринга|ВМТ]] ''M'':
-−
-<amsmath>
-\begin{split}
- x \in L &\Rightarrow P[M(x)=1]    \geq \frac{1}{2} \\
- x \notin L &\Rightarrow P[M(x)=0] > \frac{1}{2} \\
-\end{split}
-</amsmath>
-−
-или
-−
-<amsmath>
-\begin{split}
- x \in L &\Rightarrow P[M(x)=1]    > \frac{1}{2} \\
- x \notin L &\Rightarrow P[M(x)=0] \geq  \frac{1}{2} \\
-\end{split}
-</amsmath>
-−
-<h4>Диаграмма «ближайших» классов сложности</h4>
-<graph>
- digraph G{
-  NP   [URL="NP"];
-  coNP [URL="coNP"];
-  ZPP [URL="ZPP"];
-  BPP [URL="BPP"];
-  PP  [URL="PP",style="filled",fillcolor="green"];
-  RP [URL="RP"];
-  PSPACE [URL="PSPACE"];
-  coRP [URL="coRP"];
-  NEXP [URL="NEXP"];
-−
-  rankdir=LR; ranksep=0.3;
-  edge[arrowtail="none",arrowhead="crow",label=" in",fontsize=8,fontcolor="blue"];
-−
-  ZPP->RP;
-  ZPP->coRP;
-−
-  ZPP->BPP;
-−
-  coRP->BPP;
-  RP->BPP;
-−
-  coRP->coNP;
-  RP->NP;
-−
-  BPP->PP;
-−
-  coNP->PP;
-  NP->PP;
-−
-  PP->NEXP;
-  PP->PSPACE;
-−
-</graph>
-−
-−
-[[Category:Классы сложности]]
-{{replicate-from-custiswiki-to-lib}}

← Предыдущая	Версия 15:06, 6 декабря 2005
(нет различий)