Input assertion: x e L?
q1
a1
q2
Accepts /Rejects
Verifier V
(Probabilistic
Polynomial time)
Prover P
(P,V) is an interactive proof system for L if
Completeness: if x e L, then prob(V accepts) = 1-neg
Soundness: if x e L, then for all P*,
prob(V accepts) < neg
| Diapositive prÈcÈdente | Diapositive suivante | Revenir ý la premiËre diapositive | Afficher la version graphique |