# Amplifying the completeness and soundness of a proof scheme

A (interactive) proof system for a language $$\mathcal{L}$$ is defined by two algorithms $$\mathcal{P}$$, a prover, and $$\mathcal{V}$$, an efficient verifier, with the following requirements:

• Completeness: For $$x\in \mathcal{L}$$, $$\Pr[\mathcal{V}(x, \mathcal{P(x)}) = 1] \geq c$$, for some fix constant $$c \in (0,1]$$.
• Soundness: For $$x\notin \mathcal{L}$$, $$\Pr[\mathcal{V}(x, \mathcal{P(x)}) = 1] \leq s$$, for some fix constant $$s\in [0,1)$$ such that $$c-s = \delta>0$$.

Note that $$\mathcal{V}$$ does not necessarily run $$\mathcal{P}$$ as a subroutine.

It is generally stated that soundness and completeness can be "amplified" by running the proof system on the same instance $$x$$ multiple times.

Most of the time, the case of soundness is illustrated by saying that the probability that $$\mathcal{V}$$ outputs $$1$$ on all $$n$$ instances will be $$s^n$$, which to me makes sense in the case we have, for completeness, $$x\in \mathcal{L}$$, $$\Pr[\mathcal{V}(x, \mathcal{P(x)}) = 1] = 1$$. Since we know that for $$x\in \mathcal{L}$$, $$\mathcal{V}$$ is always going to output $$1$$ and when $$x\notin \mathcal{L}$$, with probability $$1-s^n$$, $$\mathcal{V}$$ will output $$0$$.

However, when $$0, how does repeating the process will help amplify the soundness? and how can it also amplify the completeness given that when $$x\in \mathcal{L}$$, it is still possible for $$\mathcal{V}$$ to output $$0$$.

I will assume that at least $$\delta$$ is known. $$c$$ can be estimated by running the proof many times on true statements and $$s$$ can be set as $$c-\delta$$. The strategy to make completeness close to $$1$$ and soundness close to $$0$$ is as follows:

• Repeat the proof $$n$$ times. Let $$v_1,\dots,v_n$$ be the output of $$\mathcal{V}$$ for each proof. If $$\sum_i v_i\geq (c-\frac\delta 2)n$$, then output $$1$$, otherwise output $$0$$.

We can show that this has the desired completeness and soundness as follows.

Completeness Assume $$x\in L$$ and let $$V_1,\dots,V_n$$ be random variables denoting the output of $$\mathcal{V}$$ for each of the repetition. We have $$\mathbb{E}[V_i]\geq c$$ for each $$i$$ by the $$c$$-completeness of the proof. The probability that we reject is $$\Pr\left[\sum_i V_i< (c-\frac\delta 2)n\right] =\Pr\left[\sum_i V_i- \mathbb{E}[\sum_i V_i]< -\frac\delta 2 n\right] \leq \exp(-\frac\delta 2 n)$$ The last inequality above is Hoeffding's inequality with $$t=\frac \delta 2 n$$.

Soundness For $$x\notin L$$, again let $$V_1,\dots,V_n$$ be random variables denoting the output of $$\mathcal{V}$$ for each of the repetition. We have $$\mathbb{E}[V_i]\leq s\leq c-\delta$$ for each $$i$$ by the $$s$$-soundness of the proof. Now, the probability that we accept is (again using Hoeffding) $$\Pr\left[\sum_i V_i\geq (c-\frac\delta 2)n\right] \leq\Pr\left[\sum_i V_i\geq (s+\frac\delta 2)n\right] =\Pr\left[\sum_i V_i- \mathbb{E}[\sum_i V_i]\geq \frac\delta 2 n\right]$$ which is again upper bounded by $$\exp(-\frac\delta 2 n)$$.

• Thank you very much. This is a really clear answer/explanation
– vxek
Sep 14 at 0:59