Difference between revisions of "Complexity Zoo:Symbols"
m (→⊕Pcc: Communication Complexity ⊕P) |
(→⊕Pcc: Communication Complexity ⊕P) |
||
Line 121: | Line 121: | ||
===== <span id="paritypcc" style="color:red">⊕P<sup>cc</sup></span>: Communication Complexity [[#parityp|⊕P]] ===== | ===== <span id="paritypcc" style="color:red">⊕P<sup>cc</sup></span>: Communication Complexity [[#parityp|⊕P]] ===== | ||
+ | |||
+ | Is not contained in [[Complexity Zoo:U#uppcc|UPP<sup>cc</sup>]] [[zooref#for02|[For02]]]. | ||
+ | |||
+ | Does not contain [[Complexity Zoo:Z#zppcc|ZPP<sup>cc</sup>]] if partial functions are allowed [[zooref#gpw16b|[GPW16b]]]. | ||
+ | |||
+ | The complexity measure associated with ⊕P<sup>cc</sup> is equivalent to the log of the rank of the communication matrix over GF(2). | ||
---- | ---- |
Latest revision as of 21:35, 9 June 2016
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}
[edit] 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].
[edit] 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.
[edit] 2-EXP: Double-Exponential Time
See EEXP.
[edit] 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.
[edit] 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}.
[edit] : Graph Automorphism
The class of problems (Karp-)reducible to counting the number of automorphisms of a graph.
Counterpart of GA.
[edit] : Sharp-L
Has the same relation to L as #P does to P.
#L is contained in DET [AJ93].
[edit] #L : Nonuniform
Has the same relation to #L as P/poly does to P.
[edit] : 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].
[edit] 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]
[edit] ⊕EXP: Parity EXP
The exponential-time analogue of ⊕P.
There exists an oracle relative to which ⊕EXP = ZPP [BBF98].
[edit] ⊕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].
The problem of simulating stabilizer circuits is complete for ⊕L [AG04].
⊕L^{⊕L} = ⊕L [BDH+92], [HRV00].
[edit] ⊕L/poly: Nonuniform ⊕L
Has the same relation to ⊕L as P/poly does to P.
[edit] ⊕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.
[edit] ⊕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).
[edit] ⊕SAC^{0}: AC^{0} With Unbounded Parity Gates
[edit] ⊕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}.