Class Description

#P: Sharp-P or Number-P

The class of function problems of the form "compute f(x)," where f is the number of accepting paths of an NP machine.

The canonical #P-complete problem is #SAT.

Defined in [Val79], where it was also shown that #Perfect Matching (or equivalently, Permanent) is #P-complete. What makes that interesting is that the associated decision problem Perfect Matching is in P.

PH is in P#P [Tod89].

Any function in #P can be approximated to within a polynomial factor in BPP with NP oracle [Sto85]. Likewise, any problem in #P can be approximated to within a constant factor by a machine in FP||NP running in time [SU05].

Linked From

#L: Sharp-L

Has the same relation to L as #P does to P.

#L is contained in the function class version of DET [AJ93]. In fact, the determinant is GapL-complete (see refs at GapL), where GapL consists of functions that are the difference of two #L functions.

More about...


#W[t]: Sharp-W[t]

Roughly, the analogue of #P for parameterized complexity. I.e. the class of parameterized counting problems that are fixed-parameter parsimonious reducible to #WSAT.Defined in [FG02], which should be consulted for the full definition. [FG02] also showed that there exist #W[1]-complete problems whose corresponding decision problems are fixed-parameter tractable (i.e. in FPT).

Complete problems for #W[1] include counting the paths or cycles of a given length in a graph and counting the chordless paths of a given length (the latter both under parsimonious and Turing reductions). Complete problems for #W[2] include the maximal chordless path problem. [CF07]

More about...


A0PP: One-Sided Analog of AWPP

Same as SBP, except that f is a nonnegative-valued GapP function rather than a #P function.

Defined in [Vya03], where the following was also shown:

Kuperberg ([Kup09]) showed that A0PP = SBQP.

More about...


AmpMP: Amplifiable MP

The class of decision problems such that for some #P function f(x,0m),

  1. The answer on input x is 'yes' if and only if the middle bit of f(x) is 1.
  2. The m bits of f(x) to the left and right of the middle bit are all 0.

Defined in [GKR+95].

Contains PH and ModPH. Contained in MP.

More about...


BPP: Bounded-Error Probabilistic Polynomial-Time

The class of decision problems solvable by an NP machine such that

  1. If the answer is 'yes' then at least 2/3 of the computation paths accept.
  2. If the answer is 'no' then at most 1/3 of the computation paths accept.

(Here all computation paths have the same length.)

Often identified as the class of feasible problems for a computer with access to a genuine random-number source.

Defined in [Gil77].

Contained in Σ2PΠ2P [Lau83], and indeed in ZPPNP [GZ97].

If BPP contains NP, then RP = NP [Ko82,Gil77] and PH is contained in BPP [Zac88].

If any problem in E requires circuits of size 2Ω(n), then BPP = P [IW97] (in other words, BPP can be derandomized).

Contained in O2P since problems requiring exponential sized circuits can be verified in O2E [GLV24] [Li23] which can be used to derandomize [IW97].

Indeed, any proof that BPP = P requires showing either that NEXP is not in P/poly, or else that #P requires superpolynomial-size arithmetic circuits [KI02].

BPP is not known to contain complete languages. [Sip82], [HH86] give oracles relative to which BPP has no complete languages.

There exist oracles relative to which P = RP but still P is not equal to BPP [BF99].

In contrast to the case of P, it is unknown whether BPP collapses to BPTIME(nc) for some fixed constant c. However, [Bar02] and [FS04] have shown hierarchy theorems for BPP with a small amount of advice.

A zero-one law exists stating that BPP has p-measure zero unless BPP = EXP [Mel00].

Equals Almost-P.

See also: BPPpath.

More about...


BPQP: Bounded-Error Probabilistic QP

Equals BPTIME(2O((log n)^k)); that is, the class of problems solvable in quasipolynomial-time on a bounded-error machine.

Defined in [CNS99], where the following was also shown:

More about...


BQP: Bounded-Error Quantum Polynomial-Time

The class of decision problems solvable in polynomial time by a quantum Turing machine, with at most 1/3 probability of error.

One can equivalently define BQP as the class of decision problems solvable by a uniform family of polynomial-size quantum circuits, with at most 1/3 probability of error [Yao93]. Any universal gate set can be used as a basis; however, a technicality is that the transition amplitudes must be efficiently computable, since otherwise one could use them to encode the solutions to hard problems (see [ADH97]).

BQP is often identified as the class of feasible problems for quantum computers.

Contains the factoring and discrete logarithm problems [Sho97], the hidden Legendre symbol problem [DHI02], the Pell's equation and principal ideal problems [Hal02], and some other problems not thought to be in BPP.

Defined in [BV97], where it is also shown that BQP contains BPP and is contained in P with a #P oracle.

BQPBQP = BQP [BV97].

[ADH97] showed that BQP is contained in PP, and [FR98] showed that BQP is contained in AWPP.

There exist oracles relative to which:

If P=BQP relative to a random oracle then BQP=BPP [FR98].

More about...


CL#P: Cluster Sharp-P

The class of #P function problems such that some underlying NP machine witnessing membership in #P has"clustered" accepting paths. That is:

Defined in [HHK+05].

More about...


coNP: Complement of NP

If NP = coNP, then any inconsistent Boolean formula of size n has a proof of inconsistency of size polynomial in n.

If NP does not equal coNP, then P does not equal NP. But the other direction is not known.

See also: NP ∩ coNP.

Every problem in coNP has an IP (interactive proof) system, where moreover the prover can be restricted to BPP#P. If every problem in coNP has an interactive protocol whose rounds are bounded by a polylogarithmic function, then EH collapses to the third level [SS04].

Co-NP is equal to SO-A, the second-order queries where the second-order quantifiers are only universals.

More about...


FPRAS: Fully Polynomial Randomized Approximation Scheme

The subclass of #P counting problems whose answer, y, is approximable in the following sense. There exists a randomized algorithm that, with probability at least 1-δ, approximates y to within an ε multiplicative factor in time polynomial in n (the input size), 1/ε, and log(1/δ).

The permanent of a nonnegative matrix is in FPRAS [JSV01].

More about...


GapL: Gap Logarithmic-Space

Has the same relation to L as GapP does to P. (And therefore, has the same relation to #L as GapP does to #P.)

The determinant is GapL-complete [Vin91] [Dam91] [Tod91] ([MV97] also gave a new, self-contained proof). See also the corresponding decision class DET

More about...


GapP: Gap Polynomial-Time

The class of functions f(x) such that for some NP machine, f(x) is the number of accepting paths minus the number of rejecting paths.

Equivalently, the closure of the #P functions under subtraction.

Defined in [FFK94] and independently [Gup95].

More about...


MP: Middle-Bit P

The class of decision problems such that for some #P function f, the answer on input x is 'yes' if and only if the middle bit of f(x) is 1.

Defined in [GKR+95].

Contains AmpMP, and ModPH, which is low for both AmpMP and MP. Contained in P#P[1].

MP with ModP oracle equals MP with #P oracle [KT96].

More about...


P#P: P With #P Oracle

I decided this class is so important that it deserves an entry of its own, apart from #P.

Contains PH [Tod89], and is contained in CH and in PSPACE.

Equals PPP (exercise for the visitor).

More about...


P#P[1]: P With Single Query To #P Oracle

Contains PH [Tod89]. Indeed, contains MP, which in turn contains ModPH [GKR+95].

More about...


PPP: P With PP Oracle

A level of the counting hierarchy CH.

It is not known whether there exists an oracle relative to which PPP does not equal PSPACE.

Contains PPPH [Tod89].

Equals P#P (exercise for the visitor).

Since the permanent of a matrix is #P-complete [Val79], Toda's theorem implies that any problem in the polynomial hierarchy can be solved by computing a sequence of permanents.

More about...


PSPACE: Polynomial-Space

The class of decision problems solvable by a Turing machine in polynomial space.

Equals NPSPACE [Sav70], AP [CKS81], and CZK assuming the existence of one-way functions [BGG+90].

Equals IP [Sha90], but PSPACE strictly contains IP with probability 1 [CCG+94].

Contains P#P (P with a #P oracle).

A canonical PSPACE-complete problem is QBF.

Relative to a random oracle, PSPACE strictly contains PH with probability 1 [Cai86].

PSPACE has a complete problem that is both downward self-reducible and random self-reducible [TV02]. It is the largest class with such a complete problem.

Contained in EXP. There exists an oracle relative to which this containment is proper [Dek76].

In descriptive complexity, PSPACE can be defined with 4 differents kind of formulae, FO() which is also FO(PFP) and SO() which is also SO(TC).

More about...


SBP: Small Bounded-Error Probability

The class of decision problems for which the following holds. There exists a #P function f and an FP function g such that, for all inputs x,

  1. If the answer is "yes" then f(x) > g(x).
  2. If the answer is "no" then f(x) < g(x)/2.

Defined in [BGM02], where the following was also shown:

There exists an oracle relative to which SBP is not closed under intersection [GLM+15].

If SAT can be solved by an NP-machine with sub-exponential number of accepting paths, then SBP = AM [Vol20].

More about...


span-L: Span Logarithmic-Space

The class of functions computable as |S|, where S is the set of output values returned by the accepting paths of an NL machine.

Defined in [AJ93], where it is also shown that span-L is a hard class in the sense that span-L is contained in FP if and only if FP = #P.

Span-L is contained in #P, and if span-L = #P, then NL = NP [AJ93].

Span-L is contained in FPRAS [ACJ+21].

More about...


span-P: Span Polynomial-Time

The class of functions computable as |S|, where S is the set of output values returned by the accepting paths of an NP machine.

Defined in [KST+89], where it is also shown that span-P contains #P and OptP; and that span-P = #P if and only if UP = NP.

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


WAPP: Weak Almost-Wide PP

The class of decision problems for which there exists a #P function f, a polynomial p, and an ε > 0, such that for all inputs x,

  1. If the answer is "yes" then 2p(|x|) ≥ f(x) > (1+ε) 2p(|x|)-1.
  2. If the answer is "no" then 0 ≤ f(x) < (1-ε) 2p(|x|)-1.

Defined in [BGM02], where it is also shown that WAPP is contained in AWPP and SBP.

More about...