108
правок
Изменения
Нет описания правки
|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> можно рассматривать как битовую цепочку логарифмической длины. Все возможные такие цепочки детерминированная МТ может сгенерировать и проверить за полиномиальное время.
