Изменения
Нет описания правки
== Свойства ==
{{Теорема
|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>: вероятностная МТ не использует случайные биты и не обращается к доказательству, то есть работает как детерминированная МТ, работающая за полиномиальное время.
