|
|
| Строка 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}} | + | |
