I'm having difficulty reading these proofs,
Definition 1 $V$ is an NP-verifier for $L$ if $V$ is polynomial-time in the length of the first input and that the following two properties hold:
- (completeness) If $x \in L$, $\exists \pi: V(x,\pi) = 1$.
- (soundness) If $x \notin L$, $\forall \pi : V(x,\pi) = 0$.
so the completeness one would be, if $x$ is an element of $L$ (part of the set $L$), there exists a $\pi$ that is ????
and the soundness one is if $x$ is not an element of $L$ (not part of the set $L$), every $\pi$ is not ????
Can anyone help me fill in the missing pieces?
Thank you
Intuitively, you should think of $V$ as an algorithm that, given $x$ and an alleged reason $\pi$ for believing that $x\in L$, either says "Yes, I'm convinced that $x\in L$" (coded as output $1$) or says "I'm not convinced; $x$ might be in $L$, but this $\pi$ doesn't convince me" (coded as output $0$). Completeness says that, if $x\in L$, then there is some way to convince $V$ to believe it, i.e., some $\pi$ that will make $V$ produce the output $1$ (meaning "I'm convinced"). Soundness says that, if $x\notin L$, then nothing can fool $V$ into thinking that $x\in L$, i.e., no matter what alleged reason $\pi$ we provide, $V$ will give output $0$ (meaning "I'm not convinced").