*Back to the Main Zoo* -*Complexity Garden* - *Zoo Glossary* - *Zoo References*

*Complexity classes by letter:*Symbols -A -B -C -D -E -F -G -H -I -J -K -L -M -N -O -P -Q -R -S -T -U -V -W -X -Y -Z

*Lists of related classes:*Communication Complexity -Hierarchies -Nonuniform

0-1-NPC -1NAuxPDAp -2-EXP -3SUM-hard -#AC0 -#L -#L/poly -#GA -#P -#W[t] -⊕EXP -⊕L -⊕L/poly -⊕P -⊕Pcc -⊕SAC0 -⊕SAC1

##### 0-1-NP_{C}: Binary Restriction of NP Over The Complex Numbers

The intersection of NPC with {0,1}^{*} (i.e. the set of binary strings).

Contains NP.

Is contained in PSPACE, and in AM assuming the Extended Riemann Hypothesis [Koi96].

##### 1NAuxPDA^{p}: One-Way NAuxPDAp

Defined in [Bra77], where it was also shown that 1NAuxPDA^{p} strictly contains CFL and is strictly contained in LOGCFL. The class corresponds to the closure of CFL under one-way log-space reductions.

##### 2-EXP: Double-Exponential Time

See EEXP.

##### 3SUM-hard: Problems hard for 3SUM

Defined in [GO95], **3SUM-hard** is the set of problems for which 3SUM is reducible to a constant number of instances of with additional time , using a real RAM model of computation as opposed to a Turing machine. That is, a problem is 3SUM-hard if 3SUM is reducible to it in sub-quadratic time.

Known to contain many problems from computational geometry, including:

**3SUM'**: do there exist such that ?**3-Points-On-Line**: given a set of points on the plane, does a line exist connecting three of them?

In [GO95], the authors list many more computational geometry problems in 3SUM-hard.

Using a model of computation strictly weaker than the real RAM machine model, a lower bound of has been shown, but this model is weak enough that not all problems in 3SUM-hard are even decidable under the model.

##### #AC^{0}: Sharp-AC0

The class of functions from {0,1}^{n} to nonnegative integers computed by polynomial-size constant-depth arithmetic circuits, using addition and multiplication gates and the constants 0 and 1.

Contained in GapAC0.

##### #GA: Graph Automorphism

The class of problems (Karp-)reducible to counting the number of automorphisms of a graph.

Counterpart of GA.

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

##### #L/poly: Nonuniform #L

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

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

##### #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]

##### ⊕EXP: Parity EXP

The exponential-time analogue of ⊕P.

There exists an oracle relative to which ⊕EXP = ZPP [BBF98].

##### ⊕L: Parity L

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

Contains SL [KW93].

Solving a linear system over Z_{2} is complete for ⊕L [Dam90].

The problem of simulating stabilizer circuits is complete for ⊕L [AG04].

⊕L^{⊕L} = ⊕L [BDH+92], [HRV00].

##### ⊕L/poly: Nonuniform ⊕L

Has the same relation to ⊕L as P/poly does to P.

Contains NL/poly [GW96].

##### ⊕P: Parity P

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

- If the answer is 'yes,' then the number of accepting paths is odd.
- If the answer is 'no,' then the number of accepting paths is even.

Defined in [PZ83].

Contains Graph Isomorphism; indeed, Graph Isomorphism is low for ⊕P [AK02].

Contains FewP [CH89].

There exists an oracle relative to which P = ⊕P but P is not equal to NP (and indeed NP = EXP) [BBF98].

Equals Mod2^mP for every positive integer m.

##### ⊕P^{cc}: Communication Complexity ⊕P

Is not contained in UPPcc [For02].

Does not contain ZPPcc if partial functions are allowed [GPW16b].

The complexity measure associated with ⊕P^{cc} is equivalent to the log of the rank of the communication matrix over GF(2).

##### ⊕SAC^{0}: AC0 With Unbounded Parity Gates

##### ⊕SAC^{1}: AC1 With Unbounded Parity Gates

The class of problems solvable by a nonuniform family of polynomial-size, polylog-depth circuits with unbounded-fanin XOR and bounded-fanin AND gates.

Defined in [GW96], where it was also shown that ⊕SAC^{1} contains SAC1.