PCP-система

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

«completeness»

, существует оракул , такой что,

«soundness»

, и для любого оракула выполняется:

---

Любые правки этой статьи будут перезаписаны при следующем сеансе репликации. Если у вас есть серьезное замечание по тексту статьи, запишите его в раздел «discussion».

Репликация: База Знаний «Заказных Информ Систем» → «PCP-система»