HiveBrain v1.2.0
Get Started
← Back to all entries
patternMinor

On the exponential hierarchy?

Submitted by: @import:stackexchange-cs··
0
Viewed 0 times
hierarchyexponentialthe

Problem

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

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

-
Does $NP=coNP\iff NEXP=coNEXP$ hold?

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

Solution

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.

Context

StackExchange Computer Science Q#85473, answer score: 2

Revisions (0)

No revisions yet.