3
$\begingroup$

The proof that $IP \subseteq PSPACE$ is done by considering by game tree of the interactions between the prover and the verifier; this tree is polynomial in depth and each message is polynomial in length, so the tree can be explored in a DFS like fashion to simulate an optimal prover in PSPACE.

Why can't the same be done for MIP? Proofs that $MIP \subseteq NEXP$ usually show that the multiple provers can be simulated by non-deterministically guessing a strategy for each, but why can't you just simulate the tree of interactions as in the single-prover case?

$\endgroup$
1
  • $\begingroup$ Hm I think I got it: when you physically draw out the tree for some communication, you see that while it's possible to represent communication from V -> (P1, P2) by an edge (and it's valid to have the value of some node of V be the average of all nodes below it), you can't represent the value of some (P1, P2) node by the max of all children since P1 and P2 are independent under the MIP model. If you try to work around this by having some sort of weird hypertree (not sure if that's the right term) then you can't evaluate in PSPACE by DFSing. $\endgroup$
    – 1110101001
    Apr 18, 2021 at 2:04

0

Your Answer

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