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.Список авторов доступен на этом ресурсе в статье под тем же названием.