Complexity Zoo:Symbols

From Complexity Zoo
Jump to: navigation, search

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-NPC: 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].

1NAuxPDAp: One-Way NAuxPDAp

Defined in [Bra77], where it was also shown that 1NAuxPDAp 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


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.

#AC0: 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 DET [AJ93].

#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 Z2 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 Mod2^mP for every positive integer m.

⊕Pcc: Communication Complexity ⊕P

Is not contained in UPPcc [For02].

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

The complexity measure associated with ⊕Pcc is equivalent to the log of the rank of the communication matrix over GF(2).

⊕SAC0: AC0 With Unbounded Parity Gates

⊕SAC1: 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 ⊕SAC1 contains SAC1.

Personal tools