Просмотр исходного текста страницы P

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

Более формально, через определение класса [[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}}