The class of decision problems for which a "yes" answer can be verified by an Arthur-Merlin protocol, as follows.
Arthur, a BPP (i.e. probabilistic polynomial-time) verifier, generates a "challenge" based on the input, and sends it together with his random coins to Merlin. Merlin sends back a response, and then Arthur decides whether to accept. Given an algorithm for Arthur, we require that
Surprisingly, it turns out that such a system is just as powerful as a private-coin one, in which Arthur does not need to send his random coins to Merlin [GS86]. So, Arthur never needs to hide information from Merlin.
Furthermore, define AM[k] similarly to AM, except that Arthur and Merlin have k rounds of interaction. Then for all constant k>2, AM[k] = AM[2] = AM [BM88]. Also, the result of [GS86] can then be stated as follows: IP[k] is contained in AM[k+2] for every k (constant or non-constant).
AM contains graph nonisomorphism.
Contains NP, BPP, and SZK, and is contained in NP/poly.AM is also contained in Π2P and this proof relativizes so the containment holds relative to any oracle.
If AM contains coNP then PH collapses to Σ2P ∩ Π2P [BHZ87].
There exists an oracle relative to which AM is not contained in PP [Ver92].
AM = NP under a strong derandomization assumption: namely that some language in NE ∩ coNE requires nondeterministic circuits of size 2Ω(n) ([MV99], improving [KM99]). (A nondeterministic circuit C has two inputs, x and y, and accepts on x if there exists a y such that C(x,y)=1.)
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.
The class of function problems of the following form:
FNP generalizes NP, which is defined in terms of decision problems only.
Actually the word "function" is misleading, since there could be many valid outputs y. That's unavoidable, since given a predicate F there's no "syntactic" criterion ensuring that y is unique.
FP = FNP if and only if P = NP.
Contains TFNP.
A basic question about FNP problems is whether they're self-reducible; that is, whether they reduce to the corresponding NP decision problems. Although this is true for all NPC problems, [BG94] shows that if EE does not equal NEE, then there is a problem in NP such that no corresponding FNP problem can be reduced to it. [BG94] cites Impagliazzo and Sudan as giving the same conclusion under the assumption that NE does not equal coNE.
Contains coNE, just as NEXP/poly contains coNEXP.
The class of problems in both NP and coNP.
Contains graph isomorphism under the assumption that some language in NE ∩ coNE requires nondeterministic circuits of size 2Ω(n) ([MV99], improving [KM99]). (A nondeterministic circuit C has two inputs, x and y, and accepts on x if there exists a y such that C(x,y)=1.)
Equals PNP ∩ coNP [Bra79]. In particular, if a problem in NP ∩ coNP is NP-hard with Turing reduction, then NP = coNP.
Is not believed to contain complete problems.
Is equal to Low(NP)={L : NPL=NP} [Sch83].