108
правок
Изменения
Нет описания правки
==PCP-система==
{{Определение
|definition =
Часто <tex>\mathrm{PCP}_{1, {}^1/{}_2}[r(n), q(n)]</tex> обозначают как <tex>\mathrm{PCP}[r(n), q(n)]</tex>.
}}
==Свойства PCP-систем==
{{Теорема
|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>
[[Недетерминированные вычисления. Классы NP и Σ₁#Классы NP и Σ₁|Определение Σ₁]]
}}
== Пример PCP-класса ==