Complexity Zoo:C - Revision history

Emil Jeřábek: /* CSIZE(f(n)): Circuit Size f(n) */ link

2024-11-06T17:01:40Z

CSIZE(f(n)): Circuit Size f(n): link

2024-11-06T16:54:54Z

CSIZE(f(n)): Circuit Size f(n): more common notation, IME

2022-11-07T17:35:56Z

adding definitions for catalytic space and catalytic logspace

2022-11-07T17:01:33Z

placement of C_k P is in the middle of CL*, which doesn't fit with either Ck or CP; moved between Check and CL#P

2022-07-19T11:01:41Z

CC0: Constant-Depth MODm Circuits

2021-06-19T22:02:24Z

2016-04-06T14:30:46Z

2016-04-06T14:19:22Z

2015-11-07T18:37:57Z

Add coNP-complete

2015-08-14T15:03:22Z

coNEXP: Complement of NEXP: updating link

@@ Line 263: / Line 263: @@
 ----
 ===== <span id="csize" style="color:red">CSIZE(f(n))</span>: Circuit Size f(n) =====
-The class of decision problems solvable by a (nonuniform) family of Boolean circuits of size O(f(n)). Often denoted just SIZE(f(n)).
+The class of decision problems solvable by a (nonuniform) family of Boolean circuits of size O(f(n)). Often denoted just [[Complexity Zoo:S#size|SIZE(f(n))]].
 So for example, CSIZE(poly(n)) (the union of CSIZE(n<sup>k</sup>) over all k) equals [[Complexity Zoo:P#ppoly|P/poly]].

@@ Line 263: / Line 263: @@
 ----
 ===== <span id="csize" style="color:red">CSIZE(f(n))</span>: Circuit Size f(n) =====
-The class of decision problems solvable by a (nonuniform) family of Boolean circuits of size O(f(n)).
+The class of decision problems solvable by a (nonuniform) family of Boolean circuits of size O(f(n)). Often denoted just SIZE(f(n)).
 So for example, CSIZE(poly(n)) (the union of CSIZE(n<sup>k</sup>) over all k) equals [[Complexity Zoo:P#ppoly|P/poly]].
@@ Line 270: / Line 270: @@
 ----
 ===== <span id="csl" style="color:red">CSL</span>: Context Sensitive Languages =====
 The class of languages generated by context-sensitive grammars.

@@ Line 87: / Line 87: @@
 See [[zooref#tor91|[Tor91]]] or [[zooref#aw90|[AW90]]] for more information.
 ----
@@ Line 282: / Line 290: @@
 In [[zooref#fv93|[FV93]]], where the class is defined, the authors show that every problem in [[Complexity Zoo:M#mmsnp|MMSNP]] is reducible under randomized polynomial-time reductions to a problem in CSP.
 ----

@@ Line 71: / Line 71: @@
 [[zooref#bg94|[BG94]]] show that if [[Complexity Zoo:N#nee|NEE]] is not contained in [[Complexity Zoo:B#bpee|BPEE]] then [[Complexity Zoo:N#np|NP]] is not contained in Check.
 ----
@@ Line 98: / Line 87: @@
 See [[zooref#tor91|[Tor91]]] or [[zooref#aw90|[AW90]]] for more information.
 ----

@@ Line 34: / Line 34: @@
 The set of problems solvable by by constant-depth circuits having only MOD<sub>''m''</sub> gates for constant <math>m</math>.
-{{CZ-Class-Stub}}
+It was shown in [[zooref#cw22|[CW22]]] that any symmetric function can be computed by depth-3 CC<sup>0</sup> circuits with size 2<sup>O(n<sup>a</sup>)</sup> for any constant a. Such a circuit uses a modulus m with size at most (1/a)<sup>2/a</sup>.
 ----

@@ Line 52: / Line 52: @@
 Contained in [[Complexity Zoo:P#pspace|PSPACE]].
-Strictly contains DLOGTIME-uniform NC<sup>1</sup> [[zooref#CMTV98|[CMTV98]]].
+Strictly contains DLOGTIME-uniform TC<sup>0</sup> [[zooref#CMTV98|[CMTV98]]].
 It is an open problem whether there exists an oracle relative to which CH is infinite, or even unequal to [[Complexity Zoo:P#pspace|PSPACE]].  This is closely related to the problem of whether [[Complexity Zoo:T#tc0|TC<sup>0</sup>]] = {{zcls|n|nc1|NC<sup>1</sup>}}, since a padding argument shows that [[Complexity Zoo:T#tc0|TC<sup>0</sup>]] = {{zcls|n|nc1|NC<sup>1</sup>}} implies CH = {{zcls|p|pspace}}.

@@ Line 245: / Line 245: @@
 ----
-===== <span id="cqsigma2p" style="color:red">cq-&#931;<sub>2</sub></span>: Classical-Quantum-[[Complexity Zoo:S#sigma2p|&#931;<sub>2</sub>P]] =====
+===== <span id="cqsigma2" style="color:red">cq-&#931;<sub>2</sub></span>: Classical-Quantum-[[Complexity Zoo:S#sigma2p|&#931;<sub>2</sub>P]] =====
 A bounded-error quantum generalization of [[Complexity Zoo:S#sigma2p|&#931;<sub>2</sub>P]] in which the first proof is classical, the second proof quantum, and the verifier is a quantum circuit.

@@ Line 244: / Line 244: @@
 Contained in [[Complexity Zoo:C#cnp|CNP]].
 ----
 ===== <span id="csize" style="color:red">CSIZE(f(n))</span>: Circuit Size f(n) =====

← Older revision		Revision as of 18:37, 7 November 2015
Line 180:		Line 180:

	Co-NP is equal to [[#Complexity_Zoo:S#so\|SO-A]], the second-order queries where the second-order quantifiers are only universals.		Co-NP is equal to [[#Complexity_Zoo:S#so\|SO-A]], the second-order queries where the second-order quantifiers are only universals.
		+	----
		+
		+	===== <span id="conpc" style="color:red">coNPC</span>: [[#conp\|coNP]]-Complete =====
		+	The class of decision problems such that (1) they're in [[#conp\|coNP]] and (2) every problem in [[#conp\|coNP]] is reducible to them (under some notion of reduction). In other words, the hardest problems in [[#conp\|coNP]].
		+
	----		----

@@ Line 162: / Line 162: @@
 ----
 ===== <span id="conexp" style="color:red">coNEXP</span>: Complement of [[Complexity Zoo:N#nexp|NEXP]] =====
-Contained in [[Complexity_Zoo:N#nexppoly|NEXP/poly]] (folklore result reported in [[http://weblog.fortnow.com/ Fortnow's weblog]]).
+Contained in [[Complexity_Zoo:N#nexppoly|NEXP/poly]] (folklore result reported in [[http://oldblog.computationalcomplexity.org/2004/01/little-theorem.html Fortnow's weblog]]).
 ----