1
$\begingroup$

A language $L$ belongs to $\mathbf{IP}$ if there exists $V,P$ such that for all $Q$, $w$, $$w\in L\Rightarrow Pr[V\leftrightarrow P\text{ accepts }w]\geq2/3$$ $$w\notin L\Rightarrow Pr[V\leftrightarrow Q\text{ accepts }w]\leq1/3$$

I am trying to understand the claim that changing the $1/3$ to $0$ for the $w \notin L$ case is equivalent to having a deterministic verifier, thus reducing the class to $\mathbf{NP}$. Is this because, in this case, we could rig all of the $V$'s interactions with $P$ so that whenever $Pr[V\leftrightarrow P\text{ accepts }w]>0$, it now determinstically accepts?

If this is correct, then why can't we do a similar thing for the hypothetical situation where the $2/3$ is replaced by a $1$ (apparently doing this does not change $\mathbf{IP}$)? My intuition is that we can't make a similar modification because it would require modifying $V$'s behaviour for all $Q$. But my thoughts are bit fuzzy here...

Can someone please help clarify?

$\endgroup$
1
$\begingroup$

Suppose you have a (randomized) verifier $V$ such that, for all $Q,w$,

$$\begin{align*} w\in L &\implies \Pr[V\leftrightarrow P\text{ accepts }w]\geq2/3\\ w\notin L &\implies \Pr[V\leftrightarrow Q\text{ accepts }w]= 0. \end{align*}$$

Since $P$ is one possible value of $Q$, it follows that

$$w\notin L \implies \Pr[V\leftrightarrow P\text{ accepts }w]= 0.$$

This means that for all $w \notin L$, there is no choice of random bits such that $V\leftrightarrow P$ accepts $w$, while for all $w \in L$, there is a choice of random bits such that $V\leftrightarrow P$ accepts $w$.

This gives you a certificate for the claim that $w \in L$: namely, the random bits used during some accepting execution of $V \leftrightarrow P$ on $w$. By the above arguments, if $w \in L$, such a certificate is guaranteed to exist, whereas if $w \notin L$, no such certificate exists. $V \leftrightarrow P$ can be used as a verifier to check the certificate. Since $V \leftrightarrow P$ runs in polynomial time, we have a polynomial-sized certificate and a polynomial-time verifier for $L$, so it follows that $L$ is in NP.

This also helps answer your second question. If you change the $2/3$ to $1$ but don't change the $1/3$ to $0$, the above argument doesn't go through: you can't conclude that there is no certificate for $w \notin L$, so you no longer have a certificate and verifier for $L$.

$\endgroup$
  • $\begingroup$ Don't we still need to specify how $V$ interacts with all other $Q$ that aren't $P$? I suppose we can just set $V$ to determinstically output "reject" regardless of the input if $Q \ne P$. But how does $V$ "know" wether or not it is interacting with $P$? $\endgroup$ – theQman Mar 17 at 0:53
  • $\begingroup$ @theQman, no. You asked for a proof that $L \in NP$. I gave you such a proof. That doesn't require specifying anything about $V$. $V$ is whatever it is (the specification of $V$ presumably already implies how it behaves). I have proven that if the first two conditions in my answer hold of $V,P$, then $L \in NP$. Nothing else needs to be assumed or specified about $V$. $\endgroup$ – D.W. Mar 17 at 5:12
  • $\begingroup$ If $V$ always deterministically outputs "reject", regardless of the input or messages it receives, then the first condition won't hold; instead, you'll have $\Pr[V\leftrightarrow P\text{ accepts }w]=0$. Note that $V$ is not "told" whether it is interacting with $P$ or $Q$; it just receives messages from someone, and the algorithm specifies how $V$ should reply and whether $V$ should accept or reject. $\endgroup$ – D.W. Mar 17 at 5:13

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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