WikiSysop в 09:58, 29 июня 2011

2011-06-29T09:58:24Z

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

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

Вообще, сейчас насчитывается не менее четырехсот различных классов сложности,
например [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>

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

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

WikiSysop в 09:58, 29 июня 2011