108
правок
Изменения
Нет описания правки
==PCP-система==
{{Определение
|definition =
<tex>\mathrm{PCP}</tex>'''-системой'''(системой вероятностно проверяемых доказательств) с полнотой <tex>c(n)</tex> и обоснованностью <tex>s(n)</tex> над алфавитом <tex>\Sigma</tex> для языка <tex>L</tex>, где <tex>0 \le s(n) \le c(n) \le 1</tex>, называется пара <tex>V</tex> {{---}} [[Вероятностные вычисления. Вероятностная машина Тьюринга#Основные определения|вероятностная машина Тьюринга]] имеющая доступ к цепочке <tex>\pi \in \Sigma^{*} : |\pi| \le 2^{poly(|input|)}</tex> {{---}} доказательству, удовлетворяющая следующим свойствам:
* '''Полнота''': если <tex>x \in L</tex>, то <tex>P(V^{\pi}(x)=1) \ge c(n)</tex> для некоторой <tex>\pi</tex>.
* '''Обоснованность''': если <tex>x \notin L</tex>, то <tex>P(V^{\pi}(x)=1) \le s(n)</tex> для любой <tex>\pi</tex>.
Сложностный класс <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>.
}}
==Свойства 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>
|proof =
* <tex>\mathrm{PCP}[0, 0]</tex> = <tex>\mathrm{P}</tex>: вероятностная МТ не использует случайные биты и не обращается к доказательству, то есть является обычной детерминированной МТ, работающей за полиномиальное время.
* <tex>\mathrm{PCP}[O(log(n)), 0]</tex> = <tex>\mathrm{P}</tex>: доступ к <tex>O(log(n))</tex> случайных бит не меняет ситуации, так как все возможные строки логарифмической длины детерминированная МТ может сгенерировать и проверить за полиномиальное время.
* <tex>\mathrm{PCP}[0, O(log(n))]</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 и Σ₁|Определение Σ₁]]
}}
