Персональные инструменты
 

NP — различия между версиями

Материал из CustisWiki

Перейти к: навигация, поиск
м (реплицировано из внутренней CustisWiki)
 
м (Содержимое страницы заменено на «#REDIRECT [[discopal:{{PAGENAME}}]]»)
 
(не показана 1 промежуточная версия 1 участника)
Строка 1: Строка 1:
Класс задач, разрешимых на [[Недетерминированная машина Тьюринга|недетерминированной машине Тьюринга]] за полиномиальное время, т.е, через определение класса [[NTIME]]:
+
#REDIRECT [[discopal:{{PAGENAME}}]]
 
+
<amsmath>{\cal NP} \equiv \cup_{c>0} {\cal NTIME}(n^c)</amsmath>
+
 
+
Можно показать также эквивалентное определение через [[машина Тьюринга|детерминированную машину Тьюринга]].
+
 
+
=== Определение через детерминированную машину Тьюринга ===
+
 
+
Язык <amsmath>L \subseteq \Sigma^*</amsmath> принадлежит классу [[NP]], если существует детерминированная [[машина Тьюринга]] ''M'' и некоторый полином ''p(*)'' такие, что
+
 
+
<amsmath>
+
  L=\{ x \in \Sigma^* : \ \exists \ y, \ |y|<p(|x|)
+
        \& \ M(x,y)=1\}
+
</amsmath>
+
 
+
Слово ''y'' называется обычно «подсказкой», «свидетелем» (''witness''), «доказательством» (''proof'').
+
 
+
 
+
=== Диаграмма «ближайших» классов сложности ===
+
 
+
<graph>
+
digraph G{
+
  P [URL="P"];
+
  coNP [URL="coNP"];
+
  NP  [URL="NP",style="filled",fillcolor="green"];
+
  ZPP [URL="ZPP"];
+
  BPP [URL="BPP"];
+
  RP [URL="RP"];
+
  coRP [URL="coRP"];
+
  "PCP(log,1)" [URL="PCP"]; 
+
  "PCP(0,poly)" [URL="PCP"]; 
+
 
+
  rankdir=LR; ranksep=0.3;
+
  edge[arrowtail="none",arrowhead="crow",label=" in",fontsize=8,fontcolor="blue"];
+
 
+
  P -> ZPP;
+
 
+
  ZPP->coRP;
+
  ZPP->RP;
+
 
+
  ZPP->BPP;
+
 
+
  RP->BPP;
+
  coRP->BPP;
+
 
+
  RP->NP;
+
  coRP->coNP;
+
 
+
edge[arrowtail="none",arrowhead="none",label="equal",fontsize=8,fontcolor="blue",constraint=0,style="bold"];
+
 
+
  {rank=same; NP->"PCP(log,1)"; NP->"PCP(0,poly)"};
+
}
+
</graph>
+
 
+
 
+
 
+
 
+
[[Category:Классы сложности]]
+
{{replicate-from-custiswiki-to-lib}}
+

Текущая версия на 20:39, 13 июня 2011

  1. REDIRECT discopal:NP