|
|
| (не показаны 2 промежуточные версии 2 участников) |
| Строка 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}}
| + | |
