Изменения

Перейти к: навигация, поиск

Класс PCP

2 байта убрано, 22:54, 16 июня 2010
Определение
# <tex>\ x \notin L \Rightarrow \forall \pi : Pr(V^{\pi}(x)=1)\le \frac{1}{2} </tex>.
Можно считать, что строка <tex>\pi</tex> всегда такая, что пытается убедить <tex>V</tex> с максимальной вероятностью принять <tex>x</tex>. Если <tex>x \in L </tex>, то это происходить происходит с вероятностью 1, иначе с вероятностью не более <tex> \frac{1}{2} </tex>.
==Свойства==
Анонимный участник

Навигация