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$
$\endgroup$
3
-
1$\begingroup$ Posted to cstheory $\endgroup$– sdcvvcMay 16, 2013 at 8:01
-
$\begingroup$ Did you get anywhere? If it's an open problem, an answer to that effect may be appropriate. $\endgroup$– Raphael ♦Apr 7, 2016 at 9:05
-
$\begingroup$ One could get a different (and as far as I know, still open) question by replacing $\Sigma_{\hspace{.03 in}2}$ with SBP $\cap$ S$_{\hspace{.02 in}2}$P . $\endgroup$– user12859Apr 7, 2016 at 11:52
Add a comment
|
1 Answer
$\begingroup$
$\endgroup$
This is not known.
$NEXP = \Sigma_{2}$ means that $NP$ and $NP^{NP}$ are different. But, $MA$ seems too weak to reach that high to catch $NP^{NP}$.
