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.

StackExchange Computer Science Q#77901, answer score: 3