12
$\begingroup$

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}$.)

$\endgroup$
  • $\begingroup$ Crosspost from cs.se where it did not get an answer. $\endgroup$ – sdcvvc May 16 '13 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$ – Scott Aaronson May 16 '13 at 14:18
  • $\begingroup$ Answered on CS.SE: cs.stackexchange.com/q/11973/755 $\endgroup$ – D.W. Nov 9 '17 at 18:56

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.