https://complexityzoo.net/api.php?action=feedcontributions&user=Ericallender&feedformat=atomComplexity Zoo - User contributions [en]2024-03-29T08:52:06ZUser contributionsMediaWiki 1.35.0https://complexityzoo.net/index.php?title=Complexity_Zoo:C&diff=6734Complexity Zoo:C2021-06-19T22:02:24Z<p>Ericallender: </p>
<hr />
<div>__NOTOC__<br />
{{CZ-Letter-Menu|C}}<br />
<br />
<br />
===== <span id="cequalsac0" style="color:red">C<sub>=</sub>AC<sup>0</sup></span>: Exact-Counting [[Complexity Zoo:A#ac0|AC<sup>0</sup>]] =====<br />
The class of problems for which there exists a [[Complexity Zoo:D#diffac0|DiffAC<sup>0</sup>]] function f such that the answer is "yes" on input x if and only if f(x)=0.<br />
<br />
Equals [[Complexity Zoo:T#tc0|TC<sup>0</sup>]] and [[Complexity Zoo:P#pac0|PAC<sup>0</sup>]] under logspace uniformity [[zooref#abl98|[ABL98]]].<br />
<br />
----<br />
===== <span id="cequalsl" style="color:red">C<sub>=</sub>L</span>: Exact-Counting [[Complexity Zoo:L#l|L]] =====<br />
Has the same relation to [[Complexity Zoo:L#l|L]] as [[Complexity Zoo:C#cequalsp|C<sub>=</sub>P]] does to [[Complexity Zoo:P#p|P]].<br />
<br />
C<sub>=</sub>L<sup>C=L</sup> = L<sup>C=L</sup> [[zooref#abo99|[ABO99]]].<br />
<br />
----<br />
===== <span id="cequalsp" style="color:red">C<sub>=</sub>P</span>: Exact-Counting Polynomial-Time =====<br />
The class of decision problems solvable by an [[Complexity Zoo:N#np|NP]] machine such that the number of accepting paths exactly equals the number of rejecting paths, if and only if the answer is 'yes.'<br />
<br />
Equals [[Complexity Zoo:C#conqp|coNQP]] [[zooref#fgh98|[FGH+98]]].<br />
<br />
----<br />
<br />
===== <span id="cc" style="color:red">CC</span>: Comparator Circuits =====<br />
A <i>comparator</i> 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.<br />
<br />
CC is defined as the class of problems log-space many-one reducible to CCVP [[zooref#ms89|[MS89]]]. At present it is only known that [[Complexity Zoo:N#nl|NL]]<math>\subseteq</math>CC<math>\subseteq</math>[[Complexity Zoo:P#p|P]] [[zooref#ms89|[MS89]]]. CC is an example of a complexity class neither known to be in [[Complexity Zoo:N#nc|NC]] nor [[Complexity Zoo:P#p|P]]-complete.<br />
<br />
Natural complete problems for the CC class include Stable Marriage Problem, Stable Roommate Problem, Lex-first Maximal Matching [[zooref#sub94|[Sub94]]].<br />
<br />
----<br />
<br />
===== <span id="cc0" style="color:red">CC<sup>0</sup></span>: Constant-Depth MOD<sub>''m''</sub> Circuits =====<br />
The set of problems solvable by by constant-depth circuits having only MOD<sub>''m''</sub> gates for constant <math>m</math>.<br />
<br />
{{CZ-Class-Stub}}<br />
<br />
----<br />
<br />
===== <span id="cfl" style="color:red">CFL</span>: Context-Free Languages =====<br />
Does not equal [[Complexity Zoo:Q#qcfl|QCFL]] [[zooref#mc00|[MC00]]].<br />
<br />
Contained in [[Complexity Zoo:L#logcfl|LOGCFL]].<br />
<br />
Strictly contains [[Complexity Zoo:D#dcfl|DCFL]] [[zooref#bra77|[Bra77]]] and indeed [[Complexity Zoo:U#ucfl|UCFL]].<br />
<br />
----<br />
<br />
===== <span id="ch" style="color:red">CH</span>: Counting Hierarchy =====<br />
The union of the [[#ckp|C<sub>k</sub>P]]'s over all constant k.<br />
<br />
Contained in [[Complexity Zoo:P#pspace|PSPACE]]. <br />
<br />
Strictly contains DLOGTIME-uniform TC<sup>0</sup> [[zooref#CMTV98|[CMTV98]]].<br />
<br />
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}}.<br />
<br />
----<br />
<br />
===== <span id="check" style="color:red">Check</span>: Checkable Languages =====<br />
The class of problems such that a polynomial-time program P that allegedly solves them can be <i>checked</i> efficiently. That is, f is in Check if there exists a [[Complexity Zoo:B#bpp|BPP]] algorithm C such that for all programs P and inputs x,<br />
<ol><br />
<li>If P(y)=f(y) for all inputs y, then C<sup>P</sup>(x) (C with oracle access to P) accepts with probability at least 2/3.</li><br />
<li>If P(x) is not equal to f(x) then C<sup>P</sup>(x) accepts with probability at most 1/3.</li><br />
</ol><br />
<br />
Introduced in [[zooref#bk89|[BK89]]], where it was also shown that Check equals [[Complexity Zoo:F#frip|frIP]] &#8745; [[Complexity Zoo:C#cofrip|cofrIP]].<br />
<br />
Check is contained in [[Complexity Zoo:N#nexp|NEXP]] &#8745; [[Complexity Zoo:C#conexp|coNEXP]] [[zooref#frs88|[FRS88]]].<br />
<br />
[[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.<br />
<br />
----<br />
===== <span id="clsharpp" style="color:red">CL#P</span>: Cluster Sharp-P =====<br />
The class of [[Complexity Zoo:Symbols#sharpp|#P]] function problems such that some underlying [[Complexity Zoo:N#np|NP]] machine <math>M</math> witnessing membership in [[Complexity Zoo:Symbols#sharpp|#P]] has<br />
"clustered" accepting paths. That is:<br />
<ul><br />
<li>There exists a polynomial <math>p</math> such that each computation path of <math>M</math> on each input <math>x</math> is exactly <math>p(|x|)</math> bits long.</li><br />
<li>There is a length-respecting total order <math>A</math> having polynomial-time computable adjacency checks on the computation paths of <math>M</math>.</li><br />
<li>The accepting paths of <math>M</math> on any input <math>x</math> are contiguous with respect to <math>A</math>.</li><br />
</ul><br />
Defined in [[zooref#hhk05|[HHK+05]]].<br />
<br />
----<br />
<br />
===== <span id="ckp" style="color:red">C<sub>k</sub>P</span>: k<sup>th</sup> Level of [[Complexity Zoo:C#ch|CH]] =====<br />
Defined as follows:<br />
<ul><br />
<li>C<sub>0</sub>P = [[Complexity Zoo:P#p|P]]</li><br />
<li>C<sub>1</sub>P = [[Complexity Zoo:P#pp|PP]]</li><br />
<li>C<sub>2</sub>P = [[Complexity Zoo:P#pp|PP]]<sup>[[Complexity Zoo:P#pp|PP]]</sup></li><br />
<li>In general, C<sub>k+1</sub>P is [[Complexity Zoo:P#pp|PP]] with C<sub>k</sub>P oracle</li><br />
</ul><br />
The union of the C<sub>k</sub>P's is called the counting hierarchy, [[Complexity Zoo:C#ch|CH]].<br />
<br />
Defined in [[zooref#wag86|[Wag86]]].<br />
<br />
See [[zooref#tor91|[Tor91]]] or [[zooref#aw90|[AW90]]] for more information.<br />
<br />
----<br />
===== <span id="clog" style="color:red">CLOG</span>: Continuous Logarithmic-Time =====<br />
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 [[Complexity Zoo:N#nc1|NC<sup>1</sup>]] formula, with n parameters that represent the input. The point to which the ODE converges (assuming it does) is the output.<br />
<br />
Defined in [[zooref#bsf02|[BSF02]]], which should be consulted for more details.<br />
<br />
[[zooref#bsf02|[BSF02]]] show that finding the maximum of n integers is in CLOG. Thus, CLOG is best thought of as the continuous-time analog of [[Complexity Zoo:N#nc1|NC<sup>1</sup>]], not of [[Complexity Zoo:D#dtime|DTIME]](log n).<br />
<br />
Contained in [[#cp|CP]].<br />
<br />
----<br />
<br />
===== <span id="cnp" style="color:red">CNP</span>: Continuous [[Complexity Zoo:N#np|NP]] =====<br />
A nondeterministic analog of [[Complexity Zoo:C#cp|CP]]. Defined in [[zooref#sf98|[SF98]]], which should be consulted for the definition (it has something to do with strange attractors, I think).<br />
<br />
The authors raise the question of whether [[Complexity Zoo:C#cp|CP]] equals CNP.<br />
<br />
----<br />
<br />
===== <span id="coam" style="color:red">coAM</span>: Complement of [[Complexity Zoo:A#am|AM]] =====<br />
<br />
----<br />
===== <span id="cocequalsp" style="color:red">coC<sub>=</sub>P</span>: Complement of [[Complexity Zoo:C#cequalsp|C<sub>=</sub>P]] =====<br />
Equals [[Complexity Zoo:N#nqp|NQP]] [[zooref#fgh98|[FGH+98]]].<br />
<br />
----<br />
===== <span id="cofrip" style="color:red">cofrIP</span>: Complement of [[Complexity Zoo:F#frip|frIP]] =====<br />
<br />
----<br />
===== <span id="coh" style="color:red">Coh</span>: Coherent Languages =====<br />
The class of problems L that are <i>efficiently autoreducible</i>, in the sense that given an input x and access to an oracle for L, a [[Complexity Zoo:B#bpp|BPP]] machine can compute L(x) by querying L only on points that differ from x.<br />
<br />
Defined in [[zooref#yao90b|[Yao90b]]].<br />
<br />
[[zooref#bg94|[BG94]]] show that, assuming [[Complexity Zoo:N#nee|NEE]] is not contained in [[Complexity Zoo:B#bpee|BPEE]], Coh &#8745; [[Complexity Zoo:N#np|NP]] is not contained in any of [[#compnp|compNP]], [[#check|Check]], or [[Complexity Zoo:F#frip|frIP]].<br />
<br />
----<br />
===== <span id="coma" style="color:red">coMA</span>: Complement of [[Complexity Zoo:M#ma|MA]] =====<br />
<br />
----<br />
===== <span id="comodkp" style="color:red">coMod<sub>k</sub>P</span>: Complement of [[Complexity Zoo:M#modkp|Mod<sub>k</sub>P]] =====<br />
<br />
----<br />
===== <span id="compip" style="color:red">compIP</span>: Competitive [[Complexity Zoo:I#ip|IP]] Proof System =====<br />
Same as [[#compnp|compNP]] but for interactive ([[Complexity Zoo:I#ip|IP]]) proofs instead of [[Complexity Zoo:N#np|NP]] proofs.<br />
<br />
More formally, compIP is the class of decision problems L in [[Complexity Zoo:I#ip|IP]] = [[Complexity Zoo:P#pspace|PSPACE]] such that, if the answer is "yes," then that can be proven by an interactive protocol between a [[Complexity Zoo:B#bpp|BPP]] verifier and a prover, a [[Complexity Zoo:B#bpp|BPP]] machine with access only to an oracle for L.<br />
<br />
Assuming [[Complexity Zoo:N#nee|NEE]] is not contained in [[Complexity Zoo:B#bpee|BPEE]], [[Complexity Zoo:N#np|NP]] (and indeed [[Complexity Zoo:N#np|NP]] &#8745; [[Complexity Zoo:C#coh|Coh]]) is not contained in [[Complexity Zoo:C#compip|compIP]] [[zooref#bg94|[BG94]]].<br />
<br />
----<br />
<br />
===== <span id="compnp" style="color:red">compNP</span>: Competitive [[Complexity Zoo:N#np|NP]] Proof System =====<br />
The class of decision problems L in [[Complexity Zoo:N#np|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.<br />
<br />
Contains [[Complexity Zoo:N#npc|NPC]].<br />
<br />
[[zooref#bg94|[BG94]]] show that compNP is contained in [[Complexity Zoo:F#frip|frIP]], and that assuming [[Complexity Zoo:N#nee|NEE]] is not contained in [[Complexity Zoo:B#bpee|BPEE]], compNP does not equal [[Complexity Zoo:N#np|NP]].<br />
<br />
----<br />
===== <span id="cone" style="color:red">coNE</span>: Complement of [[Complexity Zoo:N#ne|NE]] =====<br />
<br />
----<br />
===== <span id="conexp" style="color:red">coNEXP</span>: Complement of [[Complexity Zoo:N#nexp|NEXP]] =====<br />
Contained in [[Complexity_Zoo:N#nexppoly|NEXP/poly]] (folklore result reported in [[http://oldblog.computationalcomplexity.org/2004/01/little-theorem.html Fortnow's weblog]]).<br />
<br />
----<br />
<br />
===== <span id="conl" style="color:red">coNL</span>: Complement of [[Complexity Zoo:N#nl|NL]] =====<br />
Equals [[Complexity Zoo:N#nl|NL]] [[zooref#imm88|[Imm88]]] [[zooref#sze87|[Sze87]]].<br />
<br />
----<br />
===== <span id="conp" style="color:red">coNP</span>: Complement of [[Complexity Zoo:N#np|NP]] =====<br />
If [[Complexity Zoo:N#np|NP]] = coNP, then any inconsistent Boolean formula of size n has a proof of inconsistency of size polynomial in n.<br />
<br />
If [[Complexity Zoo:N#np|NP]] does not equal coNP, then [[Complexity Zoo:P#p|P]] does not equal [[Complexity Zoo:N#np|NP]]. But the other direction is not known.<br />
<br />
See also: [[Complexity Zoo:N#npiconp|NP &#8745; coNP]].<br />
<br />
Every problem in coNP has an [[Complexity Zoo:I#ip|IP]] (interactive proof) system, where moreover the prover can be restricted to [[Complexity Zoo:B#bpp|BPP]]<sup>[[Complexity Zoo:Symbols#sharpp|#P]]</sup>. If every problem in coNP has an interactive protocol whose rounds are bounded by a polylogarithmic function, then {{zcls|e|eh}} collapses to the third level {{zcite|SS04}}.<br />
<br />
Co-NP is equal to [[#Complexity_Zoo:S#so|SO-A]], the second-order queries where the second-order quantifiers are only universals.<br />
----<br />
<br />
===== <span id="conpc" style="color:red">coNPC</span>: [[#conp|coNP]]-Complete =====<br />
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]].<br />
<br />
----<br />
<br />
===== <span id="conpcc" style="color:red">coNP<sup>cc</sup></span>: Complement of [[Complexity Zoo:N#npcc|NP<sup>cc</sup>]] =====<br />
<br />
----<br />
===== <span id="conppoly" style="color:red">coNP/poly</span>: Complement of [[Complexity Zoo:N#nppoly|NP/poly]] =====<br />
If [[Complexity Zoo:N#np|NP]] is contained in coNP/poly then [[Complexity Zoo:P#ph|PH]] collapses to [[Complexity Zoo:S#s2p|S<sub>2</sub>P]]<sup>[[Complexity Zoo:N#np|NP]]</sup> [[zooref#cch01|[CCH+01]]].<br />
<br />
<table border="2"><tr><td>[[Complexity Zoo:N#np|NP]]<sup>[[Complexity Zoo:N#np|NP]]^[[Complexity Zoo:N#np|NP]]^([[#conppoly|coNP/poly]] &#8745; [[Complexity Zoo:N#np|NP]])</sup> = [[Complexity Zoo:N#np|NP]]<sup>[[Complexity Zoo:N#np|NP]]^[[Complexity Zoo:N#np|NP]]</sup> [[zooref#hno96|[HNO+96]]]</td></tr></table><br />
<br />
<i>Note:</i> At the suggestion of Luis Antu&ntilde;es, the above specimen of the Complexity Zoo has been locked in a cage.<br />
<br />
----<br />
===== <span id="conqp" style="color:red">coNQP</span>: Complement of [[Complexity Zoo:N#nqp|NQP]] =====<br />
Equals [[Complexity Zoo:C#cequalsp|C<sub>=</sub>P]] [[zooref#fgh98|[FGH+98]]].<br />
<br />
----<br />
===== <span id="core" style="color:red">coRE</span>: Complement of [[Complexity Zoo:R#re|RE]] =====<br />
Does not equal [[Complexity Zoo:R#re|RE]].<br />
<br />
The problem "given a computable predicate P, is P true of all positive integers?" is coRE-complete.<br />
<br />
----<br />
===== <span id="cornc" style="color:red">coRNC</span>: Complement of [[Complexity Zoo:R#rnc|RNC]] =====<br />
Contains the problem of whether a bipartite graph has a perfect matching [[zooref#kar86|[Kar86]]].<br />
<br />
----<br />
===== <span id="corp" style="color:red">coRP</span>: Complement of [[Complexity Zoo:R#rp|RP]] =====<br />
Defined in [[zooref#gil77|[Gil77]]]. (This paper does not actually discuss coRP, other than implicitly mentioning that ZPP = RP ∩ co-RP. Is there a better reference?)<br />
<br />
Contains the problem of testing whether an integer is prime [[zooref#ss77|[SS77]]].<br />
<br />
----<br />
<br />
===== <span id="cosl" style="color:red">coSL</span>: Complement of [[Complexity Zoo:S#sl|SL]] =====<br />
<br />
----<br />
===== <span id="cosparse" style="color:red">coSPARSE</span>: Complement of [[Complexity Zoo:S#sparse|SPARSE]] =====<br />
<br />
----<br />
===== <span id="coucc" style="color:red">coUCC</span>: Complement of [[Complexity Zoo:U#ucc|UCC]] =====<br />
[[zooref#tor00|[Tor00]]] showed the following problem complete for coUCC under [[Complexity Zoo:L#l|L]] reductions:<br />
<ul><br />
Given a colored graph G with at most two vertices having any given color, does G have any nontrivial automorphisms?<br />
</ul><br />
<br />
----<br />
===== <span id="coup" style="color:red">coUP</span>: Complement of [[Complexity Zoo:U#up|UP]] =====<br />
<br />
----<br />
===== <span id="cp" style="color:red">CP</span>: Continuous [[Complexity Zoo:P#p|P]] =====<br />
Same as [[#clog|CLOG]], except that the convergence time can be polynomial rather than logarithmic in the input size.<br />
<br />
Defined in [[zooref#bsf02|[BSF02]]] and [[zooref#sf98|[SF98]]].<br />
<br />
Finding a maximum flow, which is [[Complexity Zoo:P#p|P]]-complete, can be done in CP [[zooref#bsf02|[BSF02]]]. Based on this the authors argue that "[[Complexity Zoo:P#p|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 [[Complexity Zoo:P#p|P]]" (i.e. the class of ODE's they consider can be integrated efficiently on a standard Turing machine), but this is open.<br />
<br />
Contained in [[Complexity Zoo:C#cnp|CNP]].<br />
<br />
----<br />
===== <span id="cqsigma2" style="color:red">cq-&#931;<sub>2</sub></span>: Classical-Quantum-[[Complexity Zoo:S#sigma2p|&#931;<sub>2</sub>P]] =====<br />
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.<br />
<br />
Defined in [[zooref#gk14|[GK14]]].<br />
<br />
The following problems are complete for cq-&#931;<sub>2</sub> (the first two are, in addition, strongly hard to approximate for cq-&#931;<sub>2</sub>) [[zooref#gk14|[GK14]]]:<br />
QUANTUM SUCCINCT SET COVER, QUANTUM IRREDUNDANT, cq-&#931;<sub>2</sub>LH (a quantum generalization of the canonical [[Complexity Zoo:S#sigma2p|&#931;<sub>2</sub>P]]-complete problem &#931;<sub>i</sub>SAT). 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?<br />
----<br />
===== <span id="csize" style="color:red">CSIZE(f(n))</span>: Circuit Size f(n) =====<br />
The class of decision problems solvable by a (nonuniform) family of Boolean circuits of size O(f(n)).<br />
<br />
So for example, CSIZE(poly(n)) (the union of CSIZE(n<sup>k</sup>) over all k) equals [[Complexity Zoo:P#ppoly|P/poly]].<br />
<br />
Defined in [[zooref#sm02|[SM02]]] among other places.<br />
<br />
----<br />
===== <span id="csl" style="color:red">CSL</span>: Context Sensitive Languages =====<br />
The class of languages generated by context-sensitive grammars.<br />
<br />
Equals [[Complexity Zoo:N#nspace|NSPACE]](n) [[zooref#kur64|[Kur64]]].<br />
<br />
----<br />
<br />
===== <span id="csp" style="color:red">CSP</span>: Constraint Satisfaction Problems =====<br />
Defined in [[zooref#fv93|[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 [[Complexity Garden#constraint-sat|Constraint Satisfaction Problem]]. Under this construction, 3SAT may be expressed as the fixed template (over the alphabet <math>\{0,1\}</math>) containing <math>C_0, C_1, C_2, C_3</math>:<br />
<br />
<math>\begin{matrix}<br />
C_0 & = & \{0,1\}^3 \backslash (0,0,0) \\<br />
C_1 & = & \{0,1\}^3 \backslash (1,0,0) \\<br />
C_2 & = & \{0,1\}^3 \backslash (1,1,0) \\<br />
C_3 & = & \{0,1\}^3 \backslash (1,1,1)<br />
\end{matrix}</math><br />
<br />
For example, a 3SAT clause <math>(x \vee y \vee \neg z)</math> is represented in the CSP construction as <math>C_1(z, x, y) \in I</math>. By similar constructions, any k-SAT problem can be seen to be in CSP. The class also includes Graph k-Coloring (for <math>k\in\mathbb{N}</math>), Graph H-Coloring (for some graph <math>H</math>) and Linear Programming mod <math>q</math>.<br />
<br />
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.<br />
<br />
----<br />
<br />
===== <span id="czk" style="color:red">CZK</span>: Computational Zero-Knowledge =====<br />
Same as [[Complexity Zoo:S#szk|SZK]], except that now the two distributions are merely required to be <i>computationally indistinguishable</i> by any [[Complexity Zoo:B#bpp|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 <i>simulate</i> without the prover's help.)<br />
<br />
Unlike [[Complexity Zoo:S#szk|SZK]], it is not known if CZK is closed under complement. CZK is now known to share other properties with [[Complexity Zoo:S#szk|SZK]]: the verifier may as well be honest and may as well show their coins, and CZK is closed under unions [[zooref#vad06|[Vad06]]]. (Previously, these properties were only established in the presence of one-way functions [[zooref#gmw91|[GMW91]]].)<br />
<br />
Assuming the existence of one-way functions, CZK contains [[Complexity Zoo:N#np|NP]] [[zooref#gmw91|[GMW91]]], and actually equals [[Complexity Zoo:I#ip|IP]]=[[Complexity Zoo:P#pspace|PSPACE]] [[zooref#bgg90|[BGG+90]]]. However, none of these implications of one-way functions relativize (Impagliazzo, unpublished).<br />
<br />
On the other hand, if one-way functions do not exist then CZK = [[Complexity Zoo:A#avbpp|AVBPP]] [[zooref#ow93|[OW93]]].<br />
<br />
Contains [[Complexity Zoo:P#pzk|PZK]] and [[Complexity Zoo:S#szk|SZK]].</div>Ericallender