Complexity Zoo:C

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

C₌AC⁰ - C₌L - C₌P - CC - CC⁰ - CFL - CH - Check - C_kP - CL - CL#P - CLOG - CNP - coAM - coC₌P - cofrIP - Coh - coMA - coMod_kP - compIP - compNP - coNE - coNEXP - coNL - coNP - coNPC - coNP^cc - coNP/poly - coNQP - coRE - coRNC - coRP - coSL - coSPARSE - coUCC - coUP - CP - cq-Σ₂ - CSIZE(f(n)) - CSL - CSP - CSPACE - CZK

C₌AC⁰: Exact-Counting AC⁰

The class of problems for which there exists a DiffAC⁰ function f such that the answer is "yes" on input x if and only if f(x)=0.

Equals TC⁰ and PAC⁰ under logspace uniformity [ABL98].

C₌L: Exact-Counting L

Has the same relation to L as C₌P does to P.

C₌L^C=L = L^C=L [ABO99].

C₌P: Exact-Counting Polynomial-Time

The class of decision problems solvable by an NP machine such that the number of accepting paths exactly equals the number of rejecting paths, if and only if the answer is 'yes.'

Equals coNQP [FGH+98].

CC: Comparator Circuits

A comparator gate consists of two inputs and outputs the minimum of its two inputs on its first output wire and outputs the maximum of its two inputs on its second output wire. One important restriction is that each output of a comparator gate has fanout at most one. The Comparator Circuit Value Problem (CCVP) is defined as following. Given a circuit composed of comparator gates, the inputs to the circuit, and one output of the circuit, calculate the value of this output.

CC is defined as the class of problems log-space many-one reducible to CCVP [MS89]. At present it is only known that NL $\subseteq$ CC $\subseteq$ P [MS89]. CC is an example of a complexity class neither known to be in NC nor P-complete.

Natural complete problems for the CC class include Stable Marriage Problem, Stable Roommate Problem, Lex-first Maximal Matching [Sub94].

CC⁰: Constant-Depth MOD_m Circuits

The set of problems solvable by by constant-depth circuits having only MOD_m gates for constant $m$ .

It was shown in [CW22] that any symmetric function can be computed by depth-3 CC⁰ circuits with size 2^{O(n^a)} for any constant a. Such a circuit uses a modulus m with size at most (1/a)^2/a.

This is in contrast with AC0 which requires size 2^{O(n^1/(d-1))} for depth d circuits computing arbitrary symmetric functions [Has87]. Even AC0[m] for prime power m requires size 2^{O(n^1/(2d))} for depth d [Raz87] [Smo87].

CFL: Context-Free Languages

Does not equal QCFL [MC00].

Contained in LOGCFL.

Strictly contains DCFL [Bra77] and indeed UCFL.

CH: Counting Hierarchy

The union of the C_kP's over all constant k.

Contained in PSPACE.

Strictly contains DLOGTIME-uniform TC⁰ [CMTV98].

It is an open problem whether there exists an oracle relative to which CH is infinite, or even unequal to PSPACE. This is closely related to the problem of whether TC⁰ = NC¹, since a padding argument shows that TC⁰ = NC¹ implies CH = PSPACE.

Check: Checkable Languages

The class of problems such that a polynomial-time program P that allegedly solves them can be checked efficiently. That is, f is in Check if there exists a BPP algorithm C such that for all programs P and inputs x,

If P(y)=f(y) for all inputs y, then C^P(x) (C with oracle access to P) accepts with probability at least 2/3.
If P(x) is not equal to f(x) then C^P(x) accepts with probability at most 1/3.

Introduced in [BK89], where it was also shown that Check equals frIP ∩ cofrIP.

Check is contained in NEXP ∩ coNEXP [FRS88].

[BG94] show that if NEE is not contained in BPEE then NP is not contained in Check.

C_kP: k^th Level of CH

Defined as follows:

C₀P = P
C₁P = PP
C₂P = PP^PP
In general, C_k+1P is PP with C_kP oracle

The union of the C_kP's is called the counting hierarchy, CH.

Defined in [Wag86].

See [Tor91] or [AW90] for more information.

CL: Catalytic Logspace

The class CSPACE with work space $O(\log n)$ and catalytic space $n^{O(1)}$ .

Contains TC¹ and is contained in ZPP [BCKLS14].

Defined in [BCKLS14].

CL#P: Cluster Sharp-P

The class of #P function problems such that some underlying NP machine $M$ witnessing membership in #P has "clustered" accepting paths. That is:

There exists a polynomial $p$ such that each computation path of $M$ on each input $x$ is exactly $p(|x|)$ bits long.
There is a length-respecting total order $A$ having polynomial-time computable adjacency checks on the computation paths of $M$ .
The accepting paths of $M$ on any input $x$ are contiguous with respect to $A$ .

Defined in [HHK+05].

CLOG: Continuous Logarithmic-Time

Roughly, the class of continuous problems solvable by an ordinary differential equation (ODE) with convergence time logarithmic in the size of the input. The vector field of the ODE is specified by an NC¹ formula, with n parameters that represent the input. The point to which the ODE converges (assuming it does) is the output.

Defined in [BSF02], which should be consulted for more details.

[BSF02] show that finding the maximum of n integers is in CLOG. Thus, CLOG is best thought of as the continuous-time analog of NC¹, not of DTIME(log n).

Contained in CP.

CNP: Continuous NP

A nondeterministic analog of CP. Defined in [SF98], which should be consulted for the definition (it has something to do with strange attractors, I think).

The authors raise the question of whether CP equals CNP.

coAM: Complement of AM

coC₌P: Complement of C₌P

Equals NQP [FGH+98].

cofrIP: Complement of frIP

Coh: Coherent Languages

The class of problems L that are efficiently autoreducible, in the sense that given an input x and access to an oracle for L, a BPP machine can compute L(x) by querying L only on points that differ from x.

Defined in [Yao90b].

[BG94] show that, assuming NEE is not contained in BPEE, Coh ∩ NP is not contained in any of compNP, Check, or frIP.

coMA: Complement of MA

coMod_kP: Complement of Mod_kP

compIP: Competitive IP Proof System

Same as compNP but for interactive (IP) proofs instead of NP proofs.

More formally, compIP is the class of decision problems L in IP = PSPACE such that, if the answer is "yes," then that can be proven by an interactive protocol between a BPP verifier and a prover, a BPP machine with access only to an oracle for L.

Assuming NEE is not contained in BPEE, NP (and indeed NP ∩ Coh) is not contained in compIP [BG94].

compNP: Competitive NP Proof System

The class of decision problems L in NP such that, if the answer is "yes," then a proof can be constructed in polynomial time given access only to an oracle for L.

Contains NPC.

[BG94] show that compNP is contained in frIP, and that assuming NEE is not contained in BPEE, compNP does not equal NP.

coNE: Complement of NE

coNEXP: Complement of NEXP

Contained in NEXP/poly (folklore result reported in [Fortnow's weblog]).

coNL: Complement of NL

Equals NL [Imm88] [Sze87].

coNP: Complement of NP

If NP = coNP, then any inconsistent Boolean formula of size n has a proof of inconsistency of size polynomial in n.

If NP does not equal coNP, then P does not equal NP. But the other direction is not known.

coNPC: coNP-Complete

The class of decision problems such that (1) they're in coNP and (2) every problem in coNP is reducible to them (under some notion of reduction). In other words, the hardest problems in coNP.

coNP^cc: Complement of NP^cc

coNP/poly: Complement of NP/poly

If NP is contained in coNP/poly then PH collapses to S₂P^NP [CCH+01].

NP^{NP^NP^(coNP/poly ∩ NP)} = NP^{NP^NP} [HNO+96]

Note: At the suggestion of Luis Antuñes, the above specimen of the Complexity Zoo has been locked in a cage.

coNQP: Complement of NQP

Equals C₌P [FGH+98].

coRE: Complement of RE

Does not equal RE.

The problem "given a computable predicate P, is P true of all positive integers?" is coRE-complete.

coRNC: Complement of RNC

Contains the problem of whether a bipartite graph has a perfect matching [Kar86].

coRP: Complement of RP

Defined in [Gil77]. (This paper does not actually discuss coRP, other than implicitly mentioning that ZPP = RP ∩ co-RP. Is there a better reference?)

Contains the problem of testing whether an integer is prime [SS77].

coSL: Complement of SL

coSPARSE: Complement of SPARSE

coUCC: Complement of UCC

[Tor00] showed the following problem complete for coUCC under L reductions:

Given a colored graph G with at most two vertices having any given color, does G have any nontrivial automorphisms?

coUP: Complement of UP

CP: Continuous P

Same as CLOG, except that the convergence time can be polynomial rather than logarithmic in the input size.

Defined in [BSF02] and [SF98].

Finding a maximum flow, which is P-complete, can be done in CP [BSF02]. Based on this the authors argue that "P is contained in CP," but this seems hard to formalize, since CP is not a complexity class in the usual sense. They also conjecture that "CP is contained in P" (i.e. the class of ODE's they consider can be integrated efficiently on a standard Turing machine), but this is open.

Contained in CNP.

cq-Σ₂: Classical-Quantum-Σ₂P

A bounded-error quantum generalization of Σ₂P in which the first proof is classical, the second proof quantum, and the verifier is a quantum circuit.

Defined in [GK14].

The following problems are complete for cq-Σ₂ (the first two are, in addition, strongly hard to approximate for cq-Σ₂) [GK14]: QUANTUM SUCCINCT SET COVER, QUANTUM IRREDUNDANT, cq-Σ₂LH (a quantum generalization of the canonical Σ₂P-complete problem Σ_iSAT). The first of these roughly asks: Given a frustrated local Hamiltonian, what is the maximum number of local interaction terms which can be discarded before the resulting Hamiltonian is no longer frustrated?

CSIZE(f(n)): 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)).

So for example, CSIZE(poly(n)) (the union of CSIZE(n^k) over all k) equals P/poly.

Defined in [SM02] among other places.

CSL: Context Sensitive Languages

The class of languages generated by context-sensitive grammars.

Equals NSPACE(n) [Kur64].

CSP: Constraint Satisfaction Problems

Defined in [FV93] as the class of languages corresponding to fixed templates (where a template is a set of allowed constraints on values and variables) in the general Constraint Satisfaction Problem. Under this construction, 3SAT may be expressed as the fixed template (over the alphabet $\{0,1\}$ ) containing $C_{0},C_{1},C_{2},C_{3}$ :

${\begin{matrix}C_{0}&=&\{0,1\}^{3}\backslash (0,0,0)\\C_{1}&=&\{0,1\}^{3}\backslash (1,0,0)\\C_{2}&=&\{0,1\}^{3}\backslash (1,1,0)\\C_{3}&=&\{0,1\}^{3}\backslash (1,1,1)\end{matrix}}$

For example, a 3SAT clause $(x\vee y\vee \neg z)$ is represented in the CSP construction as $C_{1}(z,x,y)\in I$ . By similar constructions, any k-SAT problem can be seen to be in CSP. The class also includes Graph k-Coloring (for $k\in \mathbb {N}$ ), Graph H-Coloring (for some graph $H$ ) and Linear Programming mod $q$ .

In [FV93], where the class is defined, the authors show that every problem in MMSNP is reducible under randomized polynomial-time reductions to a problem in CSP.

CSPACE: Catalytic space

A catalytic Turing machine with space s and catalytic space c is defined as an ordinary Turing machine with a worktape of size s plus an additional worktape of size c, called the catalytic tape, with the restriction that the catalytic tape starts in some configuration $\tau \in \{0,1\}^{c}$ and with the restriction that every computation path of the machine ends with the catalytic tape in the same configuration $\tau$ .

CSPACE(s,c) is the class of decision problems recognizable by catalytic Turing machines with space s and catalytic space c. In most works c is exponential in s, as this is the largest amount of catalytic space which can still be addressed into by the worktape.

Defined in [BCKLS14]. Main variant studied is CL.

Can also be defined non-uniformly by way of catalytic branching programs [GKM15], but the relationship to traditional advice classes (i.e. CSPACE/poly) is unknown. In this setting the relationship between s and c is less constrained, often with s being constant.

CZK: Computational Zero-Knowledge

Same as SZK, except that now the two distributions are merely required to be computationally indistinguishable by any BPP algorithm; they don't have to be statistically close. (The "two distributions" are (1) the distribution over the verifier's view of their interaction with the prover, conditioned on the verifier's random coins, and (2) the distribution over views that the verifier can simulate without the prover's help.)

Unlike SZK, it is not known if CZK is closed under complement. CZK is now known to share other properties with SZK: the verifier may as well be honest and may as well show their coins, and CZK is closed under unions [Vad06]. (Previously, these properties were only established in the presence of one-way functions [GMW91].)

Assuming the existence of one-way functions, CZK contains NP [GMW91], and actually equals IP=PSPACE [BGG+90]. However, none of these implications of one-way functions relativize (Impagliazzo, unpublished).

On the other hand, if one-way functions do not exist then CZK = AVBPP [OW93].

Contains PZK and SZK.