# proving $IP^\star = NP$

Consider the following complexity class $IP^\star$, a variant of $IP$. A language $L$ is in $IP^\star$ if there's a proof system $(P,V)$ s.t. $V$ is a verifier runs for a polynomial time and:

$$x\in L \implies Pr[(P,V)(x) = 1] \ge 3/4 \\ x\not\in L \implies > Pr[(P,V)(x) = 1] = 0 \\$$

Prove that $NP = IP^\star$.

Note: in this definition as far as I understand, we have a single $P$ (for both cases).

Now, one side is easy ($NP\subseteq IP^\star$), since by definition $NP$ language has a perfect polynomial-verifier - so we're satisfying the demands.

The other side is the tricky one. Consider a language $L\in IP^\star$. We want to show that $L\in NP$. Obviously we shall utilize $V$ somehow. The certificate could be the "conversation" between $V$ and $P$. Then our $NP$ TM could simulate the conversation between $P$ to $V$.

Yet, that's alone isn't good enough - we have a $1/4$ probability to make a mistake if $x\in L$.

Amplifying the probability isn't good enough too. We need perfect soundness.

So maybe we shall use the non-determinism of our machine somehow?

If $x \in L$ then the probability that $(P,V)(x,r) = 1$ is positive, where $r$ is the randomness involved; the probability is over the choice of $r$. In particular, there is some $r$ such that $(P,V)(x,r) = 1$.

In contrast, when $x \notin L$, the probability that $(P,V)(x,r) = 0$. That is, there is no $r$ such that $(P,V)(x,r) = 1$.

States differently, when $x \in L$, there is some conversation for which the verifier outputs 1, whereas when $x \notin L$, there is no such conversation. Since the verifier runs in polytime, the conversation has polynomial length, and can be verified to be a valid conversation in polynomial time. This puts $L$ in NP.

What is the difference between IP* and IP? IP* has perfect soundness – when $x \notin L$, the probability of error is 0 – whereas IP has neither perfect soundness nor perfect completeness. This makes IP much stronger.

• (Note that IP turns out to be equivalent to its version with perfect completeness.) $\hspace{1.33 in}$
– user12859
Jul 14, 2017 at 0:28
• Since $P$ is not polynomial bounded (where $P$ is the honest prover), a NDTM can't necessarily compute $(P,V)(x,r)$ in polynomial time. I think you might mean that we compute $V(x,r,p)$ where $r$ is the randomness and $p$ is the response from the prover, over all possible $r$ and $p$? In this case the soundness condition should be quantified over provers as usual, rather than only referring to the honest prover. May 11, 2018 at 1:48