Персональные инструменты
 

PCP-система — различия между версиями

Материал из CustisWiki

Перейти к: навигация, поиск
м (Содержимое страницы заменено на «#REDIRECT [[discopal:{{PAGENAME}}]]»)
 
(не показаны 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}}
+

Текущая версия на 20:32, 13 июня 2011

  1. REDIRECT discopal:PCP-система