2
$\begingroup$

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?

$\endgroup$
3
$\begingroup$

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.

$\endgroup$
  • 1
    $\begingroup$ (Note that IP turns out to be equivalent to its version with perfect completeness.) $\hspace{1.33 in}$ $\endgroup$ – user12859 Jul 14 '17 at 0:28
  • $\begingroup$ 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. $\endgroup$ – stewbasic May 11 '18 at 1:48

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.