2
$\begingroup$

In the class $IP$ we have a probabilistic polytime verifier which interacts with a nondeterministic prover polynomial times and all the messages are of length polynomial of the input. We can think of this as a $BPP$ machine asking queries to a $NP$ oracle and doing its computation. All the interactions the verifier does and the messages got from the prover can be obtained by polynomially many steps from an $NP$ oracle. So overall the time complexity is still polynomial. Similarly, in any computation of $BPP^{SAT}$ machine, we can think of the verifier asking the prove the queries. Here the interactions are the queries made by the verifier.

Intuitively it feels that $IP=BPP^{NP}$ but is that true?

$\endgroup$

1 Answer 1

2
$\begingroup$

If $BPP = P$ (as is widely believed), then $BPP^{NP} = P^{NP}$. Since $IP = PSPACE$, $BPP^{NP} = IP$ would mean that $P^{NP} = PSPACE$, which seems unlikely (e.g. polynomial time hierarchy would collapse). Furthermore, Sipser–Lautemann theorem shows unconditionally that $BPP \subseteq NP^{NP}$, which means that $BPP^{NP} \subseteq (NP^{NP})^{NP} = NP^{NP}$. Thus $BPP^{NP} = IP$ would imply that $NP^{NP} = PSPACE$, which again seems unlikely for the same reasons as $P^{NP} = PSPACE$ seems unlikely.

Speaking more informally, your description of $IP$ is incorrect, since the prover is not limited to solving problems that are in $NP$ (nor is it non-deterministic in any sense). In fact, the prover is assumed to have unlimited computational power (e.g. it can solve the Halting problem). The trick is that it needs to be able to convince the Verifier with good probability (over the coins of the Verifier) that the solution it gave is correct.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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