Difference between revisions of "Complexity Zoo:C"
(→coNEXP: Complement of NEXP: updating link) 
(Add coNPcomplete) 

Line 180:  Line 180:  
CoNP is equal to [[#Complexity_Zoo:S#soSOA]], the secondorder queries where the secondorder quantifiers are only universals.  CoNP is equal to [[#Complexity_Zoo:S#soSOA]], the secondorder queries where the secondorder quantifiers are only universals.  
+    
+  
+  ===== <span id="conpc" style="color:red">coNPC</span>: [[#conpcoNP]]Complete =====  
+  The class of decision problems such that (1) they're in [[#conpcoNP]] and (2) every problem in [[#conpcoNP]] is reducible to them (under some notion of reduction). In other words, the hardest problems in [[#conpcoNP]].  
+  
    
Revision as of 14:37, 7 November 2015
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^{0}  C_{=}L  C_{=}P  CC  CC^{0}  CFL  CLOG  CH  Check  CL#P  C_{k}P  CNP  coAM  coC_{=}P  cofrIP  Coh  coMA  coMod_{k}P  compIP  compNP  coNE  coNEXP  coNL  coNP  coNP^{cc}  coNP/poly  coNQP  coRE  coRNC  coRP  coSL  coSPARSE  coUCC  coUP  CP  cqΣ_{2}  CSIZE(f(n))  CSL  CSP  CZK
C_{=}AC^{0}: ExactCounting AC^{0}
The class of problems for which there exists a DiffAC^{0} function f such that the answer is "yes" on input x if and only if f(x)=0.
Equals TC^{0} and PAC^{0} under logspace uniformity [ABL98].
C_{=}L: ExactCounting L
Has the same relation to L as C_{=}P does to P.
C_{=}L^{C=L} = L^{C=L} [ABO99].
C_{=}P: ExactCounting PolynomialTime
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 logspace manyone 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 Pcomplete.
Natural complete problems for the CC class include Stable Marriage Problem, Stable Roommate Problem, Lexfirst Maximal Matching [Sub94].
CC^{0}: ConstantDepth MOD_{m} Circuits
The set of problems solvable by by constantdepth circuits having only MOD_{m} gates for constant .
This complexity class entry is a stub. If you feel so inclined, please help out!
CFL: ContextFree Languages
Contained in LOGCFL.
Strictly contains DCFL [Bra77] and indeed UCFL.
CH: Counting Hierarchy
The union of the C_{k}P's over all constant k.
Contained in PSPACE.
Strictly contains DLOGTIMEuniform NC^{1} [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^{0} = NC^{1}, since a padding argument shows that TC^{0} = NC^{1} implies CH = PSPACE.
Check: Checkable Languages
The class of problems such that a polynomialtime 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.
CL#P: Cluster SharpP
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 lengthrespecting total order having polynomialtime computable adjacency checks on the computation paths of .
 The accepting paths of on any input are contiguous with respect to .
Defined in [HHK+05].
C_{k}P: k^{th} Level of CH
Defined as follows:
The union of the C_{k}P's is called the counting hierarchy, CH.
Defined in [Wag86].
See [Tor91] or [AW90] for more information.
CLOG: Continuous LogarithmicTime
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^{1} 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 continuoustime analog of NC^{1}, 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
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_{k}P: Complement of Mod_{k}P
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
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].
CoNP is equal to SOA, the secondorder queries where the secondorder quantifiers are only universals.
coNPC: coNPComplete
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_{2}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
coRE: Complement of RE
Does not equal RE.
The problem "given a computable predicate P, is P true of all positive integers?" is coREcomplete.
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 ∩ coRP. 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 Pcomplete, 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(n^{k}) over all k) equals P/poly.
Defined in [SM02] among other places.
CSL: Context Sensitive Languages
The class of languages generated by contextsensitive 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 kSAT problem can be seen to be in CSP. The class also includes Graph kColoring (for ), Graph HColoring (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 polynomialtime reductions to a problem in CSP.
CZK: Computational ZeroKnowledge
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 oneway functions [GMW91].)
Assuming the existence of oneway functions, CZK contains NP [GMW91], and actually equals IP=PSPACE [BGG+90]. However, none of these implications of oneway functions relativize (Impagliazzo, unpublished).
On the other hand, if oneway functions do not exist then CZK = AVBPP [OW93].