PCP-система
Материал из CustisWiki
PCP-cистемой, т. е. системой вероятностной проверки доказательств (от Probability Checkable Proof) для языка L, называется вероятностная машина Тьюринга с оракулом M, для которой выполняются следующие условия:
- «completeness»
- , существует оракул , такой что,
- «soundness»
- , и для любого оракула выполняется:
Любые правки этой статьи будут перезаписаны при следующем сеансе репликации. Если у вас есть серьезное замечание по тексту статьи, запишите его в раздел «discussion».
Репликация: База Знаний «Заказных Информ Систем» → «PCP-система»