Class Description

coNE: Complement of NE

Linked From

AM: Arthur-Merlin

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

  1. If the answer is "yes," then Merlin can act in such a way that Arthur accepts with probability at least 2/3 (over the choice of Arthur's random bits).
  2. If the answer is "no," then however Merlin acts, Arthur will reject with probability at least 2/3.

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

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


FNP: Function NP

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.

More about...


NE/poly: Nonuniform NE

Contains coNE, just as NEXP/poly contains coNEXP.

More about...


NP ∩ coNP

The class of problems in both NP and coNP.

Contains factoring [Pra75].

Contains graph isomorphism under the assumption that some language in NEcoNE 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].

More about...