PCP-система

Материал из свободной русской энциклопедии «Традиция»
Перейти к: навигация, поиск

PCP-cистемой, т. е. системой вероятностной проверки доказательств (от Probability Checkable Proof) для языка L, называется вероятностная машина Тьюринга с оракулом M, для которой выполняются следующие условия:

«completeness»
<amsmath>\forall x \in L</amsmath>, существует оракул <amsmath>\pi_x</amsmath>, такой что, <amsmath>
P[M^{\pi_x}(x)=1]=1

</amsmath>

«soundness»
<amsmath>\forall x \notin L</amsmath>, и для любого оракула <amsmath>\pi</amsmath> выполняется:<amsmath>
  P[M^{\pi}(x)=1] \leq \frac{1}{2}

</amsmath>
По крайней мере часть этого текста взята с ресурса http://lib.custis.ru/ под лицензией GDFL.Список авторов доступен на этом ресурсе в статье под тем же названием.