https://discopal.ispras.ru/index.php?action=history&feed=atom&title=P
P - История изменений
2026-04-20T11:10:55Z
История изменений этой страницы в вики
MediaWiki 1.26.4
https://discopal.ispras.ru/index.php?title=P&diff=803&oldid=prev
WikiSysop: 1 версия
2008-08-04T09:55:49Z
<p>1 версия</p>
<p><b>Новая страница</b></p><div>Класс задач, разрешимых на [[Машина Тьюринга|машине Тьюринга]] за полиномиальное время.<br />
<br />
Более формально, через определение класса [[DTIME]]:<br />
<br />
<amsmath>{\cal P} \equiv \cup_{c>0} {\cal DTIME}(n^c)</amsmath><br />
<br />
В современной теории сложности вычислений<br />
понятие полиномиального алгоритма является<br />
крайне удачным и адекватным математическим уточнением интуитивного<br />
понятия «эффективный алгоритм».<br />
<br />
Тем самым класс '''P''' представляет собой класс эффективно решаемых задач.<br />
<br />
<h4>Диаграмма «ближайших» классов сложности</h4><br />
<br />
<graph><br />
digraph G{<br />
P [URL="P",style="filled",fillcolor="green"];<br />
NP [URL="NP"];<br />
coNP [URL="coNP"];<br />
ZPP [URL="ZPP"];<br />
BPP [URL="BPP"];<br />
RP [URL="RP"];<br />
coRP [URL="coRP"];<br />
"PCP(log,q=2)" [URL="PCP"]; <br />
<br />
rankdir=LR; ranksep=0.3;<br />
edge[arrowtail="none",arrowhead="crow",label=" in",fontsize=8,fontcolor="blue"];<br />
<br />
P -> ZPP;<br />
<br />
ZPP->RP;<br />
ZPP->coRP;<br />
<br />
ZPP->BPP;<br />
<br />
coRP->BPP;<br />
RP->BPP;<br />
<br />
coRP->coNP;<br />
RP->NP;<br />
<br />
edge[arrowtail="none",arrowhead="none",label="equal",fontsize=8,fontcolor="blue",constraint=0,style="bold"];<br />
<br />
{rank=same; P->"PCP(log,q=2)"};<br />
}<br />
</graph><br />
<br />
<br />
<br />
<br />
[[Category:Классы сложности]]<br />
{{replicate-from-custiswiki-to-lib}}</div>
WikiSysop