= Completeness of an interactive proof
{title2=$c(n)$}
\b[Completeness of an interactive proof] guarantees that true statements can convince the <verifier in an interactive proof> when the designated <prover in an interactive proof> follows the protocol. For an <interactive proof system> for a set $L$, a bound $c(|x|)$ requires
$$
x\in L\implies\Pr[V\text{ accepts }\langle P,V\rangle(x)]\geq c(|x|).
$$
Perfect completeness means acceptance probability one on every true input. This is different from <soundness of an interactive proof>, which concerns every cheating strategy on false inputs.<Proofs that Yield Nothing But Their Validity or All Languages in NP Have Zero-Knowledge Proof Systems by Oded Goldreich and others>[Definitions of interactive proof systems, honest-prover completeness condition]{ref}
An original three-run example shows that a repetition rule changes the guarantee. Suppose three independent runs on a true statement each accept with probability $c=0.9$. Requiring all three to accept gives
$$
\Pr(\text{all accept})=c^3=0.729.
$$
Accepting when a majority does gives
$$
\Pr(\text{at least two accept})
=c^3+3c^2(1-c)=0.972.
$$
The coefficient $3$ counts which one of the three runs rejects in an exactly-two-acceptance outcome. These stipulated independent trials illustrate the aggregation rule; the soundness of the majority rule must be assessed separately.
Thus lowering the chance of false acceptance is not the only design objective. A verifier that always rejects has excellent false-statement behavior but no useful completeness. A successful proof system needs both sides of its acceptance guarantee.
Back to article page
