108
правок
Изменения
Новая страница: «{{Определение |definition = PCP-системой(системой вероятностно проверяемых доказательств) с пол...»
{{Определение
|definition =
PCP-системой(системой вероятностно проверяемых доказательств) с полнотой <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>.
}}
|definition =
PCP-системой(системой вероятностно проверяемых доказательств) с полнотой <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>.
}}
