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

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

Материал из CustisWiki

Перейти к: навигация, поиск
м (реплицировано из внутренней CustisWiki)
 
м (Содержимое страницы заменено на «#REDIRECT [[discopal:{{PAGENAME}}]]»)
 
(не показана 1 промежуточная версия 1 участника)
Строка 1: Строка 1:
Класс-дополнение к классу [[NP]].
+
#REDIRECT [[discopal:{{PAGENAME}}]]
 
+
<amsmath>
+
co{\cal NP} \equiv \{L|\overline{L} \in {\cal NP}\}
+
</amsmath>
+
 
+
=== Определение через детерминированную машину Тьюринга ===
+
 
+
Язык <amsmath>L \subseteq \Sigma^*</amsmath> принадлежит классу [[coNP]], если существует детерминированная [[машина Тьюринга]] ''M'' и некоторый полином ''p(*)'' такие, что
+
 
+
<amsmath>
+
  L=\{ x \in \Sigma^* : \ \forall \ y, \ |y|<p(|x|)
+
        \ \ M(x,y)=0\}
+
</amsmath>
+
 
+
 
+
===Диаграмма «ближайших» классов сложности===
+
 
+
<graph>
+
digraph G{
+
  P [URL="P"];
+
  NP  [URL="NP"];
+
  coNP [URL="coNP",style="filled",fillcolor="green"];
+
  ZPP [URL="ZPP"];
+
  BPP [URL="BPP"];
+
  PP  [URL="PP"];
+
  RP [URL="RP"];
+
  coRP [URL="coRP"];
+
 
+
 
+
  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;
+
 
+
  BPP->PP;
+
 
+
  coNP->PP;
+
  NP->PP;
+
}
+
</graph>
+
 
+
 
+
 
+
[[Category:Классы сложности]]
+
{{replicate-from-custiswiki-to-lib}}
+

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

  1. REDIRECT discopal:CoNP