# Does the MIP* = RE proof work for limited provers?

MIP* = RE shows that two arbitrarily strong entangled provers can convince a verifier of instances of the halting problem. Now assume that we have two entangled provers that are only capable of solving problems in some language $$L$$ (say a language complete for NEEXP, NEEEXP, etc.).

Question: What constraints on $$L$$ allow provers to convince a verifier of solutions to $$L$$?

The nonquantum analogy is that not only is IP = PSPACE, but IP' = PSPACE where IP' provers are only able to solve PSPACE level problems. In particular, L = PSPACE works for the MIP* question. Moreover, provers that are limited to any level of the polynomial hierarchy $$\Sigma_k \textrm{P}$$ can establish $$\Sigma_k \textrm{P} \subset \textrm{PSPACE}$$. (Unfortunately, looks like this doesn't work lower in the polynomial hierarchy.)

(I'm blurring over some definitional subtlety here about function problems vs. decision problems; in the above one probably needs the provers to be able to solve $$\textrm{FP}^L$$ rather than just L.)

• Thank you! To clarify: your first statement seems much stronger than the second due to $T$ being the same in both occurrences of NTIME. Would there be some blowup? Jan 21 '20 at 21:38
• Reasonable to conjecture that for suitably large $T$ the blowup disappears? Jan 22 '20 at 14:00