Complexity Zoo:C

From Complexity Zoo
Revision as of 17:35, 7 November 2022 by Iwmertz (talk | contribs) (adding definitions for catalytic space and catalytic logspace)
(diff) ← Older revision | Latest revision (diff) | Newer revision → (diff)
Jump to navigation Jump to 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

C=AC0 - C=L - C=P - CC - CC0 - CFL - CLOG - CH - Check - CL#P - CkP - CNP - coAM - coC=P - cofrIP - Coh - coMA - coModkP - compIP - compNP - coNE - coNEXP - coNL - coNP - coNPcc - coNP/poly - coNQP - coRE - coRNC - coRP - coSL - coSPARSE - coUCC - coUP - CP - cq-Σ2 - CSIZE(f(n)) - CSL - CSP - CZK

C=AC0: Exact-Counting AC0

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

Equals TC0 and PAC0 under logspace uniformity [ABL98].

C=L: Exact-Counting L

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

C=LC=L = LC=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 NLCCP [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].

CC0: Constant-Depth MODm Circuits

The set of problems solvable by by constant-depth circuits having only MODm gates for constant .

It was shown in [CW22] that any symmetric function can be computed by depth-3 CC0 circuits with size 2O(na) 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 2O(n1/(d-1)) for depth d circuits computing arbitrary symmetric functions [Has87]. Even AC0[m] for prime power m requires size 2O(n1/(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 CkP's over all constant k.

Contained in PSPACE.

Strictly contains DLOGTIME-uniform TC0 [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 TC0 = NC1, since a padding argument shows that TC0 = NC1 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,

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

Introduced in [BK89], where it was also shown that Check equals frIPcofrIP.

Check is contained in NEXPcoNEXP [FRS88].

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

CkP: kth Level of CH

Defined as follows:

  • C0P = P
  • C1P = PP
  • C2P = PPPP
  • In general, Ck+1P is PP with CkP oracle

The union of the CkP'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 and catalytic space .

Contains TC1 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 witnessing membership in #P has "clustered" accepting paths. That is:

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

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 NC1 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 NC1, 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

coModkP: Complement of ModkP

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 NPCoh) 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.

See also: NP ∩ coNP.

Every problem in coNP has an IP (interactive proof) system, where moreover the prover can be restricted to BPP#P. If every problem in coNP has an interactive protocol whose rounds are bounded by a polylogarithmic function, then EH collapses to the third level [SS04].

Co-NP is equal to SO-A, the second-order queries where the second-order quantifiers are only universals.

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.

coNPcc: Complement of NPcc

coNP/poly: Complement of NP/poly

If NP is contained in coNP/poly then PH collapses to S2PNP [CCH+01].

NPNP^NP^(coNP/polyNP) = NPNP^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-Σ2: Classical-Quantum-Σ2P

A bounded-error quantum generalization of Σ2P 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-Σ2 (the first two are, in addition, strongly hard to approximate for cq-Σ2) [GK14]: QUANTUM SUCCINCT SET COVER, QUANTUM IRREDUNDANT, cq-Σ2LH (a quantum generalization of the canonical Σ2P-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)).

So for example, CSIZE(poly(n)) (the union of CSIZE(nk) 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 ) containing :

For example, a 3SAT clause is represented in the CSP construction as . By similar constructions, any k-SAT problem can be seen to be in CSP. The class also includes Graph k-Coloring (for ), Graph H-Coloring (for some graph ) and Linear Programming mod .

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 and with the restriction that every computation path of the machine ends with the catalytic tape in the same configuration .

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.