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)$

  1. (Completeness) For every $x \in {0,1}^n$

$Pr[out(V, x, r, P) = 1] \ge 1 - \delta_c$

  1. (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?


1 Answer 1


This is arbitrary. The definition of the class does not change as long as the $\delta$s are sufficiently away from $1/2$, where 'sufficiently' means by a non-negligible value in $n$, as they can be amplified (by, e.g., parallel repetition) to be overwhelmingly close to $1$. $1/3$ satisfies this criterion. See the discussion after the definition in the Wikipedia article about the class $\mathbf{BPP}$.


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.