108
правок
Изменения
Нет описания правки
|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}(</tex> допустит <tex>x)=1) \ge </tex>, не меньше <tex>c(n)</tex> для некоторой <tex>\pi</tex>.* '''Обоснованность''': если <tex>x \notin L</tex>, то вероятность того, что <tex>P(V^{\pi}(</tex> допустит <tex>x)=1) \le </tex>, не больше <tex>s(n)</tex> для любой <tex>\pi</tex>.
}}
{{Определение
{{Определение
|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}[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>: так как доступа к случайным битам нет, доказательство <tex>\pi</tex> можно рассматривать как строку битовую цепочку логарифмической длины. Все возможные такие строки цепочки детерминированная МТ может сгенерировать и проверить за полиномиальное время.
}}
{{Теорема
