# Complexity Zoo:Symbols

*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-NP_{C} -
1NAuxPDA^{p} -
2-EXP -
3SUM-hard -
#AC^{0} -
#L -
#L/poly -
#GA -
#P -
#W[t] -
⊕EXP -
⊕L -
⊕L/poly -
⊕P -
⊕P^{cc} -
⊕SAC^{0} -
⊕SAC^{1}

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

The intersection of NP_{C} 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 NAuxPDA^{p}

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-

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 GapAC^{0}.

##### : Graph Automorphism

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

Counterpart of GA.

##### : Sharp-L

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

#L is contained in DET [AJ93].

##### #L : Nonuniform

Has the same relation to #L as P/poly does to 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.

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-

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.

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

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

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

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

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

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

Equals Mod_{2^m}P for every positive integer m.

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

##### ⊕SAC^{1}: AC^{1} 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 SAC^{1}.