143
правки
Изменения
→Свойства: PCP теорема, анонс
|proof =
Очевидно следует из [[Классы_NP_и_Σ₁|определения Σ₁]].
}}
{{Теорема
|id=pcp_th
|about=[[PCP-теорема]]
|statement=<tex>\mathrm{PCP}[log(n), O(1)] = \mathrm{NP}</tex>
|proof=
В одну сторону включение тривиально <tex>\mathrm{PCP}(\log n, 1) \subseteq \mathrm{NTIME}(2^{O(\log n)}) = NP</tex>.
Обратное включение <tex>NP \subseteq \mathrm{PCP}(\log n, 1)</tex> нетривиально и рассматривается в [[PCP-теорема | PCP-теореме]].
}}
