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⁰ - #L - #L/poly - #GA - #P - #W[t] - ⊕EXP - ⊕L - ⊕L/poly - ⊕P - ⊕P^cc - ⊕SAC⁰ - ⊕SAC¹

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 $P$ for which 3SUM is reducible to a constant number of instances of $P$ with additional time $o(n^{2})$, 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 $a,b,c$ such that $a+b=c$?
• 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 $\Omega (n^{2})$ has been shown, but this model is weak enough that not all problems in 3SUM-hard are even decidable under the model.

---

#AC⁰: Sharp-AC⁰

The class of functions from {0,1}ⁿ 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⁰.

---

#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 $\epsilon$ by a machine in FP^||NP running in $\mathrm {poly} (n,\epsilon ^{-1})$ 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₂ 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

1. If the answer is 'yes,' then the number of accepting paths is odd.
2. 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 Mod_2^mP for every positive integer m.

---

⊕P^cc: Communication Complexity ⊕P

Is not contained in UPP^cc [For02].

Does not contain ZPP^cc 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¹: AC¹ 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¹ contains SAC¹.