Изменения

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

Класс IP

1 байт добавлено, 16:33, 6 мая 2010
Определение
1) <tex>x \in L \Rightarrow Pr(V^{P}(x)=1)\ge \frac{2}{3} \ </tex> , где <tex>Pr(V^{P}(x)=1)</tex> - вероятность того, что <tex>P</tex> убедит <tex>V</tex> допуститить <tex>x</tex>
2) <tex>\forall Q :\ x \notin L \Rightarrow \forall Q : Pr(V^{Q}(x)=1)\le \frac{1}{3} </tex>
3) количество обращений к <tex>P \le f(n) </tex>
Анонимный участник

Навигация