The Equivalency of Two Definitions of Completeness & Soundness in Interactive Proof Systems The completeness and soundness in interactive proof systems are informally defined as:


Completeness: If a statement is true, the honest prover can convince the honest verifier of this fact w.h.p.
Soundness: If a statement is false, the cheating prover cannot convince the honest verifier (of the validity of the false statement) w.h.p.


The term "w.h.p." is either interpreted as "with probability greater than (say) 2/3," or "with probability greater than the reciprocal of any polynomial." It seems immaterial to the following discussion as what interpretation of "w.h.p." to choose.

The tricky part is how the probability is computed: In some sources, the probability is taken over the random coins of both the prover and the verifier. In other sources, the probability is only computed over the random coins of the verifier. The latter is usually justified as: "whatever the random coins of the prover are, the verifier makes the right decision."

To me, both definitions of probability seem equivalent; yet I can't prove this. Am I right? Can you prove them equivalent?
The prover is "all-powerful and possesses unlimited computational resources" so it has no need of random bits. Thus the only randomness is the randomness of the verifier.

If the prover uses random bits, it should replace them with the random bit string that is most likely to make the verifier accept (this is true for both the honest and any dishonest prover). Furthermore, the prover can determine this optimal bit string because the prover is "all-powerful".