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

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

2011-06-13T17:39:10Z

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

WikiSysop: 1 версия

2008-08-04T09:55:49Z

1 версия

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

2005-12-07T04:40:36Z

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

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

Класс задач, разрешимых на [[Машина Тьюринга|машине Тьюринга]] за полиномиальное время.

Более формально, через определение класса [[DTIME]]:

<amsmath>{\cal P} \equiv \cup_{c>0} {\cal DTIME}(n^c)</amsmath>

В современной теории сложности вычислений
понятие полиномиального алгоритма является
крайне удачным и адекватным математическим уточнением интуитивного
понятия «эффективный алгоритм».

Тем самым класс '''P''' представляет собой класс эффективно решаемых задач.

<h4>Диаграмма «ближайших» классов сложности</h4>

<graph>
digraph G{
P [URL="P",style="filled",fillcolor="green"];
NP [URL="NP"];
coNP [URL="coNP"];
ZPP [URL="ZPP"];
BPP [URL="BPP"];
RP [URL="RP"];
coRP [URL="coRP"];
"PCP(log,q=2)" [URL="PCP"];

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;

edge[arrowtail="none",arrowhead="none",label="equal",fontsize=8,fontcolor="blue",constraint=0,style="bold"];

{rank=same; P->"PCP(log,q=2)"};
}
</graph>

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

StasFomin в 14:48, 6 декабря 2005

2005-12-06T14:48:11Z

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

@@ Строка 1: / Строка 1: @@
-Класс задач, разрешимых на [[Машина Тьюринга|машине Тьюринга]] за полиномиальное время.
+#REDIRECT [[discopal:{{PAGENAME}}]]
-−
-Более формально, через определение класса [[DTIME]]:
-−
-<amsmath>{\cal P} \equiv \cup_{c>0} {\cal DTIME}(n^c)</amsmath>
-−
-В современной теории сложности вычислений
-понятие полиномиального алгоритма является
-крайне удачным и адекватным математическим уточнением интуитивного
-понятия «эффективный алгоритм».
-−
-Тем самым класс '''P''' представляет собой класс эффективно решаемых задач.
-−
-<h4>Диаграмма «ближайших» классов сложности</h4>
-−
-<graph>
- digraph G{
-  P [URL="P",style="filled",fillcolor="green"];
-  NP   [URL="NP"];
-  coNP [URL="coNP"];
-  ZPP [URL="ZPP"];
-  BPP [URL="BPP"];
-  RP [URL="RP"];
-  coRP [URL="coRP"];
-  "PCP(log,q=2)" [URL="PCP"];
-−
-  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;
-−
-edge[arrowtail="none",arrowhead="none",label="equal",fontsize=8,fontcolor="blue",constraint=0,style="bold"];
-−
-  {rank=same; P->"PCP(log,q=2)"};
-−
-</graph>
-−
-−
-−
-−
-[[Category:Классы сложности]]
-{{replicate-from-custiswiki-to-lib}}

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