1
$\begingroup$

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<c<1$, 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$.

$\endgroup$

1 Answer 1

1
$\begingroup$

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

$\endgroup$
1
  • $\begingroup$ Thank you very much. This is a really clear answer/explanation $\endgroup$
    – vxek
    Commented Sep 14, 2023 at 0:59

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.