PCP-система
Материал из DISCOPAL
PCP-cистемой, т. е. системой вероятностной проверки доказательств (от Probability Checkable Proof) для языка L, называется вероятностная машина Тьюринга с оракулом M, для которой выполняются следующие условия:
- «completeness»
- , существует оракул , такой что,
- «soundness»
- , и для любого оракула выполняется:
[ Хронологический вид ]Комментарии
Войдите, чтобы комментировать.