From a text on Interactive Proofs
$x \in {0,1}^n$ is input
$V$ is verifier
$P$ is prover
$r$ is $V$'s internal randomness
$P$ provides a value $y$ which is claimed to be equal to $f(x)$
- (Completeness) For every $x \in {0,1}^n$
$Pr[out(V, x, r, P) = 1] \ge 1 - \delta_c$
- (Soundness) For every $x \in {0,1}^n$ and every deterministic prover strategy $P'$, if $P'$ sends a value $y \ne f(x)$ at the start of the protocol, then
$Pr[out(V,x,r;P') = 1] \le \delta_s$
An interactive proof system is valid if $\delta_c, \delta_s \le \frac 13$
What is the significance of $\frac 13$ here? Why has $\frac 13$ been chosen as the what the 2 $\delta$s have to be lesser than? I mean why not $\frac 14$ or $\frac 12$ or something else?