|
|
| (не показаны 2 промежуточные версии 2 участников) |
| Строка 1: |
Строка 1: |
| − | '''PCP-cистемой''', т. е. системой вероятностной проверки доказательств (от ''Probability Checkable Proof'') для языка ''L'', называется [[вероятностная машина Тьюринга]] с оракулом ''M'', для которой выполняются следующие условия:
| + | #REDIRECT [[discopal:{{PAGENAME}}]] |
| − | | + | |
| − | ;«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>
| + | |
| − | | + | |
| − | [[Category:Теория сложности]]
| + | |
| − | {{replicate-from-custiswiki-to-lib}}
| + | |
