https://discopal.ispras.ru/index.php?title=NP&feed=atom&action=history
NP - История изменений
2024-03-28T18:20:35Z
История изменений этой страницы в вики
MediaWiki 1.26.4
https://discopal.ispras.ru/index.php?title=NP&diff=797&oldid=prev
WikiSysop: 1 версия
2008-08-04T09:55:49Z
<p>1 версия</p>
<p><b>Новая страница</b></p><div>Класс задач, разрешимых на [[Недетерминированная машина Тьюринга|недетерминированной машине Тьюринга]] за полиномиальное время, т.е, через определение класса [[NTIME]]:<br />
<br />
<amsmath>{\cal NP} \equiv \cup_{c>0} {\cal NTIME}(n^c)</amsmath><br />
<br />
Можно показать также эквивалентное определение через [[машина Тьюринга|детерминированную машину Тьюринга]].<br />
<br />
=== Определение через детерминированную машину Тьюринга ===<br />
<br />
Язык <amsmath>L \subseteq \Sigma^*</amsmath> принадлежит классу [[NP]], если существует детерминированная [[машина Тьюринга]] ''M'' и некоторый полином ''p(*)'' такие, что<br />
<br />
<amsmath><br />
L=\{ x \in \Sigma^* : \ \exists \ y, \ |y|<p(|x|)<br />
\& \ M(x,y)=1\}<br />
</amsmath><br />
<br />
Слово ''y'' называется обычно «подсказкой», «свидетелем» (''witness''), «доказательством» (''proof'').<br />
<br />
<br />
=== Диаграмма «ближайших» классов сложности ===<br />
<br />
<graph><br />
digraph G{<br />
P [URL="P"];<br />
coNP [URL="coNP"];<br />
NP [URL="NP",style="filled",fillcolor="green"];<br />
ZPP [URL="ZPP"];<br />
BPP [URL="BPP"];<br />
RP [URL="RP"];<br />
coRP [URL="coRP"];<br />
"PCP(log,1)" [URL="PCP"]; <br />
"PCP(0,poly)" [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->coRP;<br />
ZPP->RP;<br />
<br />
ZPP->BPP;<br />
<br />
RP->BPP;<br />
coRP->BPP;<br />
<br />
RP->NP;<br />
coRP->coNP;<br />
<br />
edge[arrowtail="none",arrowhead="none",label="equal",fontsize=8,fontcolor="blue",constraint=0,style="bold"];<br />
<br />
{rank=same; NP->"PCP(log,1)"; NP->"PCP(0,poly)"};<br />
}<br />
</graph><br />
<br />
<br />
<br />
<br />
[[Category:Классы сложности]]<br />
{{replicate-from-custiswiki-to-lib}}</div>
WikiSysop