Class Description

NP/poly: Nonuniform NP

Has the same relation to NP as P/poly does to P.

Contains AM. On the other hand, if NP/poly contains coNP then PH collapses to the third level.

NP/poly-natural proofs cannot show that circuit families are outside P/poly, under a pseudorandomness assumption [Rud97].

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


coNP/poly: Complement of NP/poly

If NP is contained in coNP/poly then PH collapses to S2PNP [CCH+01].

NPNP^NP^(coNP/polyNP) = NPNP^NP [HNO+96]

Note: At the suggestion of Luis Antuñes, the above specimen of the Complexity Zoo has been locked in a cage.

More about...


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


NPC: NP Over The Complex Numbers

An analog of NP for Turing machines over a complex number field.

Defined in [BCS+97].

It is unknown whether PC = NPC, nor are implications known among this question, PR versus NPR, and P versus NP.

However, [CKK+95] show that if P/poly does not equal NP/poly then PC does not equal NPC.

[BCS+97] show the following striking result. For a positive integer n, let t(n) denote the minimum number of additions, subtractions, and multiplications needed to construct n, starting from 1. If for every sequence {nk} of positive integers, t(nk k!) grows faster than polylogarithmically in k, then PC does not equal NPC.

See also VNPk.

More about...


(NP ∩ coNP)/poly: Nonuniform NP ∩ coNP

Together with NP/poly ∩ coNP/poly, has the same relation to NP ∩ coNP as P/poly has to P. A language in (NP ∩ coNP)/poly is defined by a single language in NP ∩ coNP which is then modified by advice. A language in NP/poly ∩ coNP/poly comes from two possibly different languages in NP and coNP which become the same with good advice.

There is an oracle relative to which NP/poly ∩ coNP/poly, indeed NP/1 ∩ coNP/1, is not contained in (NP ∩ coNP)/poly [FFK+93]. Recently they improved this to NP/1 ∩ coNP [FF..].

If NP is contained in (NP ∩ coNP)/poly, then PH collapses to S2PNP ∩ coNP [CCH+01].

More about...


NP/log: NP With Logarithmic Advice

Same as NP/poly, except that now the advice string is logarithmic-size.

Shown in [FK05] that EXP ⊆ NP/log if and only if EXP = P||NP.

More about...


NPR: NP Over The Reals

An analog of NP for Turing machines over a real number field.

Defined in [BCS+97].

It is unknown whether PR = NPR, nor are implications known among this question, PC versus NPC, and P versus NP.

Also, in contrast to the case of NPC, it is an open problem to show that P/poly distinct from NP/poly implies PR distinct from NPR. The difference is that in the real case, a comparison (or greater-than) operator is available, and it is not known how much power this yields in comparison to the complex case.

See also VNPk.

More about...


VNPk: Valiant NP Over Field k

A superclass of VPk in Valiant's algebraic complexity theory, but not quite the analogue of NP.

A problem is in VNPk if there exists a polynomial p with the following properties:

Originated in [Val79b].

If the field k has characteristic greater than 2, then the permanent of an n-by-n matrix of indeterminates is VNPk-complete under a type of reduction called p-projections ([Val79b]; see also [Bur00]).

A central conjecture is that for all k, VPk is not equal to VNPk. Bürgisser [Bur00] shows that if this were false then:

In both cases, PH collapses to Σ2P.

More about...