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.)
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].
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.
One of the caged classes of the Complexity Zoo.
Has been implicated in a collapse scandal involving AM[polylog], coNP, and EH.