Is it known whether the implication $\mathsf{NEXP} = \Sigma_2 \implies \mathsf{NEXP} = \mathsf{MA}$ holds?

(The question is inspired by well-known $\mathsf{NEXP} \subseteq \mathsf{P/poly} \Leftrightarrow \mathsf{NEXP} = \mathsf{MA}$.)

  • $\begingroup$ Crosspost from cs.se where it did not get an answer. $\endgroup$
    – sdcvvc
    May 16, 2013 at 8:01
  • 10
    $\begingroup$ Interesting question! All I can say is that I don't know of any result of this kind, nor do I know of any existing techniques that seem up to it. Granted, the hypothesis is extremely strong, but in some sense a collapse to Sigma_2 seems "still too high above MA's head" for MA to reach up and grab it. $\endgroup$ May 16, 2013 at 14:18
  • $\begingroup$ Answered on CS.SE: cs.stackexchange.com/q/11973/755 $\endgroup$
    – D.W.
    Nov 9, 2017 at 18:56


Your Answer

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