We know $P\subseteq PH\subseteq PSPACE\subseteq EXP\subseteq NEXP$.

  1. Is it known or believed that $\Delta_2^{exp}=EXP^{NP}\subseteq NEXP=\Sigma_1^{exp}$ and/or $EXP^{PH}\subseteq NEXP$?

  2. Does $NP=coNP\iff NEXP=coNEXP$ hold?

Note $NEXP=coNEXP\implies \Delta_2^{exp}=\Sigma_1^{exp}$?


1 Answer 1


1) Both two unbelieved scenarios that $\mathrm{NP}=\mathrm{P}$ and $\mathrm{NP}=\mathrm{EXP}$ implies that $\mathrm{EXP}^\mathrm{NP} = \mathrm{NEXP}$ and $\mathrm{EXP}^\mathrm{PH}=\mathrm{NEXP}$. So we cannot refute these two claims at present.

On the other hand,

  • assuming $\mathrm{EXP}^\mathrm{PH}=\mathrm{NEXP}$ would imply $\mathrm{BPP}\neq\mathrm{NEXP}$, since $\mathrm{BPP}\subseteq\Sigma_2^{p}$ and $\Sigma_2^p\subsetneq\mathrm{\Sigma_2^{exp}\subseteq\mathrm{EXP}^\mathrm{PH}}$

  • assuming $\mathrm{EXP}^\mathrm{NP}=\mathrm{NEXP}$ would imply $\mathrm{P}^\mathrm{NP}\neq\mathrm{NEXP}\cap\mathrm{co}-\mathrm{NEXP}$

2) First of all, your implication that $\mathrm{NEXP}=\mathrm{co}-\mathrm{NEXP}\implies\Delta_2^{exp}=\Sigma_1^{exp}$ is not known since exponential-time hierarchy does not possess the upward collapsing property like polynomial-time hierarchy (some inner collapse at some level does not necessarily imply the collapsion of all the exponential-time hierarchy to that level).

Beside from that, $\mathrm{NP}=\mathrm{co}-\mathrm{NP}\implies\mathrm{NEXP}=\mathrm{co}-\mathrm{NEXP}$ is true by standard translation technique, but the opposite implication is not known due to the difficulty in achieving the downward closure theorems for non-determinism and co-non-determinism. It has been done for probabilistic classes (zero-sided, one-sided, bounded-error all done, but general probabilistic $\mathrm{PrTime}$ still open). For more details on downward closure theorems, see the reference in this answer.


Your Answer

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

Not the answer you're looking for? Browse other questions tagged or ask your own question.