Nondeterministic exponential time with linear exponent (i.e. NTIME(2O(n))).
Contained in NEXP.
The class of multivariate polynomials over the integers that can be evaluated using a polynomial (in the input size n) number of additions, subtractions, and multiplications, together with the constants -1 and 1. The class is nonuniform, in the sense that the polynomial for each input size n can be completely different.
Named in [Imp02], though it has been considered since the 1970's.
If P = BPP (or even BPP is contained in NE), then either NEXP is not in P/poly, or else the permanent polynomial of a matrix is not in AlgP/poly [KI02].
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.)
Equals DTIME(2O(n)).
Does not equal NP [Boo72] or PSPACE [Boo74] relative to any oracle. However, there is an oracle relative to which E is contained in NP (see ZPP), and an oracle relative to PSPACE is contained in E (by equating the former with P).
There exists a problem that is complete for E under polynomial-time Turing reductions but not polynomial-time truth-table reductions [Wat87].
Problems hard for BPP under Turing reductions have measure 1 in E [AS94].
It follows that, if the problems complete for E under Turing reductions do not have measure 1 in E, then BPP does not equal EXP.
[IT89] gave an oracle relative to which E = NE but still there is an exponential-time binary predicate whose corresponding search problem is not in E.
[BF03] gave a proof that if E = NE, then no sparse set is collapsing, where they defined a set to be collapsing if and if for all such that and are Turing reducible to each other, and are many-to-one reducible to each other.
Contrast with EXP.
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].
The class of functions computable in polynomial time with a shared, untrusted witness for each input size. The input-oblivious version of NP.
L is in ONP if there exists a polynomial time verifier V taking an input and a witness, so that:
Defined in [FSW09], where it was shown NP has size nk circuits for some constant k if and only if ONP/1 has size nj circuits for some constant j.
ONP is contained in P/poly and NP [FSW09].
ONP = NP iff NP is in P/poly [FSW09].
If NE is not E then ONP is not P [GM15].
See also YP for an input oblivious analogue of NP ∩ coNP.
The union of NE, NPNE, NPNP^NE, and so on.
Is called "strong" to contrast it with the ordinary Exponential Hierarchy EH.
Note that we would get the same class if we replaced NE by NEXP.
There exists an oracle relative to which SEH is not contained in EH [Hem89].EH and SEH are incomparable for all anyone knows.
The class of languages L in NP such that the union, over all x in L, of the set of valid witnesses for x equals L itself.
Defined in [HT03], where it was shown that the closure of SelfNP under polynomial-time many-one reductions is NP.
They also show that if SelfNP = NP, then E = NE; and that SAT is contained in SelfNP.
See also: PermUP.
