Class Description

MAPOLYLOG: MA With Polylog Verifier

Identical to MA except for that Arthur (the verifier) has random access to the proof string given by Merlin, and is limited to running times of order .

This class was used by [SM03] to show that if EXP has circuits of polynomial size, then EXP = MA.

Linked From

EXP: Exponential Time

Equals the union of DTIME(2p(n)) over all polynomials p.

Also equals P with E oracle.

If L = P then PSPACE = EXP.

If EXP is in P/poly then EXP = MA [BFL91].

Problems complete for EXP under many-one reductions have measure 0 in EXP [May94], [JL95].

There exist oracles relative to which

[BT04] show the following rather striking result: let A be many-one complete for EXP, and let S be any set in P of subexponential density. Then A-S is Turing-complete for EXP.

[SM03] show that if EXP has circuits of polynomial size, then P can be simulated in MAPOLYLOG such that no deterministic polynomial-time adversary can generate a list of inputs for a P problem that includes one which fails to be simulated. As a result, EXP ⊆ MA if EXP has circuits of polynomial size.

[SU05] show that EXP NP/poly implies EXP P||NP/poly.

In descriptive complexity EXPTIME can be defined as SO() which is also SO(LFP)

More about...