Class Description

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

Linked From

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

More about...