Class Description

AM[polylog]: AM With Polylog Rounds

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.)

Linked From

AMEXP: Exponential-Time AM

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].

More about...


EH: Exponential-Time Hierarchy With Linear Exponent

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.

More about...


IP[polylog]:

More about...


S2-EXP•PNP: Don't Ask

One of the caged classes of the Complexity Zoo.

Has been implicated in a collapse scandal involving AM[polylog], coNP, and EH.

More about...