# Changing probabilities to 0/1 in definition of class IP

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

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

• 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$? – theQman Mar 17 '19 at 0:53
• @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$. – D.W. Mar 17 '19 at 5:12
• 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. – D.W. Mar 17 '19 at 5:13