108
правок
Изменения
Нет описания правки
{{Определение
|definition =
Сложностный класс <tex>\mathrm{PCP}_{c(n), s(n)}[r(n), q(n)]</tex> является объединением всех языков всех <tex>L</tex>, для которых существует <tex>\mathrm{PCP}</tex>-система над бинарным алфавитом с полнотой <tex>c(n)</tex> и обоснованностью <tex>s(n)</tex>, в которой верификатор <tex>V</tex> неадаптивный, работает за полиномиальное время и имеет вероятностную и запросную сложности соответственно <tex>r(n)</tex> и <tex>q(n)</tex>.<br/>
Часто <tex>\mathrm{PCP}_{1, {}^1/{}_2}[r(n), q(n)]</tex> обозначают как <tex>\mathrm{PCP}[r(n), q(n)]</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 и Σ₁|Определение определения Σ₁]]
}}
