Диаграмма классов сложности - История изменений

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

2011-06-13T17:38:22Z

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

WikiSysop: 1 версия

2008-12-29T11:50:27Z

1 версия

AndrewSatarin: викификация

2008-12-26T14:10:39Z

викификация

WikiSysop: 1 версия

2008-08-04T09:55:52Z

1 версия

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

2005-12-07T04:41:54Z

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

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

Диаграмма представляет отношения между основными классами сложности.
Отношения вложенности обозначены «лапками» , а эквивалентность — жирными линиями.
Диаграмма гипертекстовая — т. е. «кликая» на вершину некоторого класса, попадаешь на его определение.

Вообще, сейчас насчитывается не менее четырехсот различных классов сложности,
например [http://qwiki.caltech.edu/wiki/Complexity_Zoo Зоопарк Классов Сложности] упоминает о 442 классах.

<graph>
digraph G{
node[fontsize=10];
P [URL="P"];
NP [URL="NP"];
coNP [URL="coNP"];
ZPP [URL="ZPP"];
BPP [URL="BPP"];
PP [URL="PP"];
RP [URL="RP"];
PSPACE [URL="PSPACE"];
coRP [URL="coRP"];
NEXP [URL="NEXP"];
"PCP(log,1)" [URL="PCP"];
"PCP(0,poly)" [URL="PCP"];
"PCP(poly,0)" [URL="PCP"];
"PCP(poly,poly)" [URL="PCP"];
"PCP(log,log)" [URL="PCP"];

rankdir=TB; 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;

"PCP(0,poly)"->"PCP(poly,poly)";
"PCP(poly,0)"->"PCP(poly,poly)";
"PCP(log,1)"->"PCP(log,log)";
"PCP(log,log)"->"PCP(poly,poly)";

PP->NEXP;
PP->PSPACE;
"PCP(log,q=2)"->"PCP(log,1)";

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

P->"PCP(log,q=2)";
NP->"PCP(log,1)";
NP->"PCP(0,poly)";
coRP->"PCP(poly,0)";
"PCP(poly,poly)"->NEXP;
"PCP(log,1)"->"PCP(log,log)";
}
</graph>

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

StasFomin: {{replicate-from-custiswiki-to-lib}}

2005-12-06T14:04:00Z

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

@@ Строка 1: / Строка 1: @@
-Диаграмма представляет отношения между основными классами сложности.
+#REDIRECT [[discopal:{{PAGENAME}}]]
-Отношения вложенности обозначены «лапками», а эквивалентность — жирными линиями.
-Диаграмма гипертекстовая — то есть «кликая» на вершину некоторого класса, попадаешь на его определение.
-−
-Вообще, сейчас насчитывается не менее четырехсот различных классов сложности,
-например [http://qwiki.stanford.edu/wiki/Complexity_Zoo Зоопарк Классов Сложности] упоминает о 488 классах.
-−
-<graph>
- digraph G{
-  node[fontsize=10];
-  P [URL="P"];
-  NP   [URL="NP"];
-  coNP [URL="coNP"];
-  ZPP [URL="ZPP"];
-  BPP [URL="BPP"];
-  PP  [URL="PP"];
-  RP [URL="RP"];
-  PSPACE [URL="PSPACE"];
-  coRP [URL="coRP"];
-  NEXP [URL="NEXP"];
-  "PCP(log,1)"  [URL="PCP"];
-  "PCP(0,poly)" [URL="PCP"];
-  "PCP(poly,0)" [URL="PCP"];
-  "PCP(poly,poly)" [URL="PCP"];
-  "PCP(log,log)" [URL="PCP"];
-−
-  rankdir=TB; 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;
-−
-  "PCP(0,poly)"->"PCP(poly,poly)";
-  "PCP(poly,0)"->"PCP(poly,poly)";
-  "PCP(log,1)"->"PCP(log,log)";
-  "PCP(log,log)"->"PCP(poly,poly)";
-−
-  PP->NEXP;
-  PP->PSPACE;
-  "PCP(log,q=2)"->"PCP(log,1)";
-−
-  edge[arrowtail="none",arrowhead="none",label="equal",fontsize=8,fontcolor="blue",constraint=0,style="bold"];
-−
-  P->"PCP(log,q=2)";
-  NP->"PCP(log,1)";
-  NP->"PCP(0,poly)";
-  coRP->"PCP(poly,0)";
-  "PCP(poly,poly)"->NEXP;
-  "PCP(log,1)"->"PCP(log,log)";
-−
-</graph>
-−
-[[Категория:Классы сложности]]
-{{replicate-from-custiswiki-to-lib}}

← Предыдущая	Версия 11:50, 29 декабря 2008
(нет различий)

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