|
|
| Строка 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}}
| + | |
