1632
правки
Изменения
м
rollbackEdits.php mass rollback
== Свойства ==
{{Теорема
|statement = <tex>\mathrm{PCP}[0, 0]</tex> = <tex>\mathrm{PCP}[O(\log(n)), 0]</tex> = <tex>\mathrm{PCP}[0, O(\log(n))]</tex> = <tex>\mathrm{P}</tex>.
|proof =
* <tex>\mathrm{PCP}[0, 0]</tex> = <tex>\mathrm{P}</tex>: вероятностная МТ не использует случайные биты и не обращается к доказательству, то есть работает как детерминированная МТ, работающая за полиномиальное время.
* <tex>\mathrm{PCP}[O(\log(n)), 0]</tex> = <tex>\mathrm{P}</tex>: доступ к <tex>O(\log(n))</tex> случайных бит не меняет ситуации, так как все возможные битовые цепочки логарифмической длины детерминированная МТ может сгенерировать и проверить за полиномиальное время.* <tex>\mathrm{PCP}[0, O(\log(n))]</tex> = <tex>\mathrm{P}</tex>: так как доступа к случайным битам нет, <tex>\pi</tex> можно рассматривать как битовую цепочку логарифмической длины. Все возможные такие цепочки детерминированная МТ может сгенерировать и проверить за полиномиальное время.
}}
{{Теорема
|statement = <tex>\mathrm{PCP}[poly(n), 0]</tex> = <tex>\mathrm{coRP}</tex>.
|proof =
Очевидно следует из [[Вероятностные вычисления. Вероятностная машина ТьюрингаКлассы RP и coRP#Вероятностные сложностные классыОпределения|определения coRP]].
}}
{{Теорема
|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-теореме]].
}}
