108
правок
Изменения
Нет описания правки
== Определения ==
{{Определение
|definition =
Часто <tex>\mathrm{PCP}_{1, {}^1/{}_2}[r(n), q(n)]</tex> обозначают как <tex>\mathrm{PCP}[r(n), q(n)]</tex>.
}}
== Свойства ==
{{Теорема
|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>
}}
== Пример ==
{{Теорема
|statement = '''Graph Nonisomorphism(GNI)''' <tex>\in \mathrm{PCP}[poly(n), O(1)]</tex>
|proof =
