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>: вероятностная МТ не использует случайные биты и не обращается к доказательству, то есть является обычной детерминированной МТ, работающей за полиномиальное время.
}}
{{Теорема
|statement = <tex>\mathrm{PCP}[poly(n), 0]</tex> = <tex>\mathrm{coRP}</tex>.
|proof =
Очевидно следует из [[Вероятностные вычисления. Вероятностная машина Тьюринга#Вероятностные сложностные классы|определения coRP]].
}}
{{Теорема
|statement = <tex>\mathrm{PCP}[0, poly(n)]</tex> = <tex>\mathrm{NP}</tex>.
|proof =
Очевидно следует из [[Недетерминированные вычисления. Классы NP и Σ₁#Классы NP и Σ₁|определения Σ₁]].
== Пример ==
{{Теорема
|statement = '''Graph Nonisomorphism(GNI)''' <tex>\in \mathrm{PCP}[poly(n), O(1)]</tex>.
|proof =
<tex>G_1</tex> и <tex>G_2</tex> {{---}} графы на <tex>n</tex> вершинах. Требуется проверить, изоморфны ли они друг другу. <br/>
