Has roughly the same relationship to E as PH does to P.
More formally, EH is defined as the union of E, NE, NENP, NE with Σ2P oracle, and so on.
See [Har87] for more information.
If coNP is contained in AM[polylog], then EH collapses to S2-EXP•PNP [SS04] and indeed AMEXP [PV04].
On the other hand, coNE is contained in NE/poly, so perhaps it wouldn't be so surprising if NE collapses.
There exists an oracle relative to which EH does not contain SEH [Hem89]. EH and SEH are incomparable for all anyone knows.
Same as AM, except that Arthur is exponential-time and can exchange exponentially long messages with Merlin.
Contains MAEXP, and is contained in EH and indeed S2-EXP•PNP.
If coNP is contained in AM[polylog] then EH collapses to AMEXP [PV04].
Same as AM, except that we allow polylog(n) rounds of interaction between Arthur and Merlin instead of a constant number.
Not much is known about AM[polylog] -- for example, whether it sits in PH. However, [SS04] show that if AM[polylog] contains coNP, then EH collapses to S2-EXP•PNP. ([PV04] improved the collapse to AMEXP.)
If NP = coNP, then any inconsistent Boolean formula of size n has a proof of inconsistency of size polynomial in n.
If NP does not equal coNP, then P does not equal NP. But the other direction is not known.
See also: NP ∩ coNP.
Every problem in coNP has an IP (interactive proof) system, where moreover the prover can be restricted to BPP#P. If every problem in coNP has an interactive protocol whose rounds are bounded by a polylogarithmic function, then EH collapses to the third level [SS04].
Co-NP is equal to SO-A, the second-order queries where the second-order quantifiers are only universals.
One of the caged classes of the Complexity Zoo.
Has been implicated in a collapse scandal involving AM[polylog], coNP, and EH.
The union of NE, NPNE, NPNP^NE, and so on.
Is called "strong" to contrast it with the ordinary Exponential Hierarchy EH.
Note that we would get the same class if we replaced NE by NEXP.
There exists an oracle relative to which SEH is not contained in EH [Hem89].EH and SEH are incomparable for all anyone knows.