Class Description

NE/poly: Nonuniform NE

Contains coNE, just as NEXP/poly contains coNEXP.

Linked From

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