Why there is a probability in the completeness part?

Question

Interactive Proof System : An interactive proof system for a language $L$ is a two-party game between a verifier and a prover that interact on a common input in a way satisfying the following properties:

1. The verifier strategy is a probabilistic polynomial-time procedure (where time is measured in terms of the length of the common input)
2. Correctness requirements:
3. Completeness: There exists a prover strategy $P$, such that for every $x ∈ L$, when interacting on the common input $x$, the prover $P$ convinces the verifier with probability at least $\frac{2}{3}$.
4. Soundness: For a false assertion, no convincing proof strategy exists (in the case of NP, if $x \notin L$ then no witness $y$ exists).

My Question : In the completeness part why there is a probability comming into picture?

Answer 1

The standard definition of $\mathsf{IP}$ involves probability both in the completeness and soundness requirements. Removing randomness all together reduces $\mathsf{IP}$ to $\mathsf{NP}$ (the witness is the full accepting transcript).

Note that you can amplify the success probability by "repeating the protocol" (i.e. talking with a prover $P'$ who simulates repetitions) and taking the majority vote (you need to be slightly careful here, since your dealing with a special prover who has access to previous interactions, but you're saved by the universal quantifier in the soundness requirement).

If what's bothering you is the fact that the protocols you are familiar with satisfy completeness with probability $1$, then one example is the proof for graph non isomorphism being in $\mathsf{AM[2]}$, using the set lower bound protocol, where the completeness probability is smaller than 1.

That said, you can in fact remove the probability from the completeness requirement (i.e. say that there exists a prover which convinces $V$ with probability $1$, $V$ is still probabilistic) without changing the class $\mathsf{IP}$, but this is a non trivial fact, which follows from the protocol for TQBP in the $\mathsf{IP=PSPACE}$ proof (which succeeds with probability 1 in case the formula is true).