108
правок
Изменения
Нет описания правки
|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 и Σ₁|определения Σ₁]].
}}
