Difference between revisions of "Complexity Zoo:C"
m (1 revision: Complexity zoo import.)
Revision as of 03:10, 18 November 2012
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.
C=L: Exact-Counting L
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.'
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 .
CFL: Context-Free Languages
Contained in LOGCFL.
CH: Counting Hierarchy
The union of the CkP's over all constant k.
Contained in PSPACE.
Strictly contains DLOGTIME-uniform NC1 [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,
- 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.
- If P(x) is not equal to f(x) then CP(x) accepts with probability at most 1/3.
CL#P: Cluster Sharp-P
- 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].
CkP: kth Level of CH
Defined as follows:
The union of the CkP's is called the counting hierarchy, CH.
Defined in [Wag86].
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.
Contained in CP.
CNP: Continuous NP
The authors raise the question of whether CP equals CNP.
coAM: Complement of AM
coC=P: Complement of C=P
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].
coMA: Complement of MA
coModkP: Complement of ModkP
compIP: Competitive IP Proof System
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.
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.
coNE: Complement of NE
coNEXP: Complement of NEXP
coNL: Complement of NL
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.
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.
coNPcc: Complement of NPcc
coNP/poly: Complement of NP/poly
|NPNP^NP^(coNP/poly ∩ NP) = 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
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
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.
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.
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.
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 .
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).