View source for Complexity Zoo:D

__NOTOC__
{{CZ-Letter-Menu|D}}


===== <span id="dsharpp" style="color:red">D#P</span>: Alternate Name for [[Complexity Zoo:P#psharpp|P<sup>#P</sup>]] =====

----

===== <span id="Dp" style="color:red">D<sup>p</sup></span>: Difference for polynomial-time =====
The languages that are the interesction of a language in NP and a language in co-NP.

Contains NP and co-NP, is contained in &#916;<sub>2</sub>P.

Complete problems: Exact-Clique, SAT-UNSAT, etc.

Defined in [[zooref#yp84|[YP84]]].

----

===== <span id="dcfl" style="color:red">DCFL</span>: Deterministic [[Complexity Zoo:C#cfl|CFL]] =====
The class of languages accepted by deterministic pushdown automata.

Defined in [[zooref#gg66|[GG66]]], where it was also shown that DCFL is strictly contained in [[Complexity Zoo:C#cfl|CFL]], contained in [[Complexity Zoo:U#ucfl|UCFL]], and strictly contains [[Complexity Zoo:R#reg|REG]].  The inclusion in UCFL is also strict.

----

===== <span id="delta2p" style="color:red">&#916;<sub>2</sub>P</span>: [[Complexity Zoo:P#p|P]] With [[Complexity Zoo:N#np|NP]] Oracle =====
A level of [[Complexity Zoo:P#ph|PH]], the polynomial hierarchy.

One &#916;<sub>2</sub>P-complete problem: Given a Boolean formula, does the lexicographically last satisfying assignment end with a 1? [[zooref#kre88|[Kre88]]]

Contains [[Complexity Zoo:B#bh|BH]].

There exists an oracle relative to which &#916;<sub>2</sub>P is not contained in [[Complexity Zoo:P#pp|PP]] [[zooref#bei94|[Bei94]]].

There exists another oracle relative to which &#916;<sub>2</sub>P is contained in [[Complexity Zoo:P#ppoly|P/poly]] [[zooref#bgs75|[BGS75]]], and indeed has linear-size circuits [[zooref#wil85|[Wil85]]].

There exists an oracle B for which [[Complexity Zoo:B#bpp|BPP]]<sup>B</sup> is exponentially more powerful than &#916;<sub>2</sub>P<sup>B</sup> [[zooref#kv96|[KV96]]].

If [[Complexity Zoo:P#p|P]] = [[Complexity Zoo:N#np|NP]], then any polynomial-size circuit C can be learned in &#916;<sub>2</sub>P with C oracle [[zooref#aar06|[Aar06]]].

----

===== <span id="deltabpp" style="color:red">&#948;-BPP</span>: &#948;-Semi-Random [[Complexity Zoo:B#bpp|BPP]] =====
Same as [[Complexity Zoo:B#bpp|BPP]], except that the random bit source is biased as follows.  Each bit could depend on all the previous bits in arbitrarily complicated ways; the only promise is that the bit is 1 with probability in the range [&#948;,1-&#948;], conditioned on all previous bits.

So clearly 0-BPP = [[Complexity Zoo:P#p|P]] and 1/2-BPP = [[Complexity Zoo:B#bpp|BPP]].

It turns out that, for any &#948;&gt;0, &#948;-BPP = [[Complexity Zoo:B#bpp|BPP]] [[zooref#vv85|[VV85]]], [[zooref#zuc91|[Zuc91]]].

----
===== <span id="deltarp" style="color:red">&#948;-RP</span>: &#948;-Semi-Random [[Complexity Zoo:R#rp|RP]] =====
Same as [[#deltabpp|&#948;-BPP]], but for [[Complexity Zoo:R#rp|RP]] instead of [[Complexity Zoo:B#bpp|BPP]].

For any &#948;&gt;0, &#948;-RP = [[Complexity Zoo:R#rp|RP]] [[zooref#vv85|[VV85]]].

----
===== <span id="det" style="color:red">DET</span>: Determinant =====
The class of decision problems reducible in [[Complexity Zoo:L#l|L]] to the problem of computing the determinant of an n-by-n matrix of n-bit integers.

Defined in [[zooref#coo85|[Coo85]]]. (Cook used [[Complexity Zoo:N#nc1|NC<sup>1</sup>]] reductions in his definition)

Contained in [[Complexity Zoo:N#nc2|NC<sup>2</sup>]], and contains [[Complexity Zoo:N#nl|NL]] and [[Complexity Zoo:P#pl|PL]] [[zooref#bcp83|[BCP83]]].

[[Complexity_Garden#graph_isomorphism|Graph isomorphism]] is hard for DET under [[Complexity Zoo:L#l|L]]-reductions [[zooref#tor00|[Tor00]]].

The corresponding function class turns out to be equal to [[Complexity Zoo:G#gapl|GapL]] (see refs at [[Complexity Zoo:G#gapl|GapL]]), that is, the determinant of integer matrices is GapL-complete.

----

===== <span id="diffac0" style="color:red">DiffAC<sup>0</sup></span>: Difference [[Complexity Zoo:Symbols#sharpac0|#AC<sup>0</sup>]] =====
The class of functions from {0,1}<sup>n</sup> to integers expressible as the difference of two [[Complexity Zoo:Symbols#sharpac0|#AC<sup>0</sup>]] functions.

Equals [[Complexity Zoo:G#gapac0|GapAC<sup>0</sup>]] under logspace uniformity [[zooref#abl98|[ABL98]]].

----
===== <span id="disnp" style="color:red">DisNP</span>: Disjoint [[Complexity Zoo:N#np|NP]] Pairs =====
The class of pairs (A,B), where A and B are [[Complexity Zoo:N#np|NP]] problems whose sets of "yes" instances are nonempty and disjoint.

If there exists an optimal propositional proof system, then DisNP has a complete pair [[zooref#raz94|[Raz94]]].  On the other hand, there exists an oracle relative to which DisNP does not have a complete pair [[zooref#gss03|[GSS+03]]].

If [[Complexity Zoo:P#p|P]] does not equal [[Complexity Zoo:U#up|UP]], then DisNP contains pairs not separated by any set in [[Complexity Zoo:P#p|P]] [[zooref#gs88|[GS88]]].  On the other hand, there exists an oracle relative to which [[Complexity Zoo:P#p|P]] does not equal [[Complexity Zoo:N#np|NP]] but still DisNP does not contain any [[Complexity Zoo:P#p|P]]-inseparable pairs [[zooref#hs92|[HS92]]].

----
===== <span id="distnp" style="color:red">DistNP</span>: Distributional [[Complexity Zoo:N#np|NP]] =====
(also called (NP,P-computable) or RNP)

A <i>distributional problem</i> consists of a decision problem A, and a probability distribution &#956; over problem instances.

(A,&#956;) is in DistNP if A is in [[Complexity Zoo:N#np|NP]], and &#956; is [[Complexity Zoo:P#p|P]]-computable (meaning that its cumulative density function can be evaluated in polynomial time).

DistNP has complete problems [[zooref#lev86|[Lev86]]] (see also [[zooref#gur87|[Gur87]]]), although unlike for [[Complexity Zoo:N#np|NP]] this is not immediate.

Any DistNP-complete problem is also complete for [[Complexity Zoo:N#nppsamp|(NP,P-samplable)]] [[zooref#il90|[IL90]]].

----

===== <span id="dp" style="color:red">DP</span>: Difference Polynomial-Time =====
DP = [[Complexity Zoo:B#bh|BH]]<sub>2</sub>, the second level of the Boolean hierarchy.

Defined in [[zooref#py84|[PY84]]].

----

===== <span id="dqc1" style="color:red">DQC1</span>: Deterministic Quantum Computing with 1 Clean Bit =====
The class of problems solvable by a [[Complexity Zoo:B#bqp|BQP]] machine in which a single qubit is initialized to the '0' state, and the remaining qubits are initialized to the maximally mixed state.

We need to stipulate that there are no "strong measurements" -- intermediate measurements on which later operations are conditioned -- since otherwise we can do all of [[Complexity Zoo:B#bqp|BQP]] by first initializing the computer to the all-0 state.

[[zooref#asv00|[ASV00]]] showed that if DQC1 = [[Complexity Zoo:B#bqp|BQP]], something other than gate-by-gate simulation will be needed to show this.

[[zooref#sj08|[SJ08]]] showed that approximating the Jones polynomial at a fifth root of unity for the trace closure of a braid is complete for DQC1.

----

===== <span id="dqp" style="color:red">DQP</span>: Dynamical Quantum Polynomial-Time =====
The class of decision problems solvable by a [[Complexity Zoo:B#bqp|BQP]] machine with oracle access to a <i>dynamical simulator</i>. When given a polynomial-size quantum circuit, the simulator returns a sample from the distribution over "classical histories" induced by the circuit. The simulator can adversarially choose any history distribution that satisfies the axioms of "symmetry" and "locality" -- so that the DQP algorithm has to work for any distribution satisfying these axioms.

See [[zooref#aar05|[Aar05]]] for a full definition.

There it is also shown that [[Complexity Zoo:S#szk|SZK]] is contained in DQP.

Contains [[Complexity Zoo:B#bqp|BQP]], and is contained in [[Complexity Zoo:E#exp|EXP]] [[zooref#aar05|[Aar05]]].

There exists an oracle relative to which DQP does not contain [[Complexity Zoo:N#np|NP]] [[zooref#aar05|[Aar05]]].

----

===== <span id="dspace" style="color:red">DSPACE(f(n))</span>: Deterministic f(n)-Space =====
The class of decision problems solvable by a Turing machine in space O(f(n)).

The Space Hierarchy Theorem: For constructible f(n) greater than log
n, DSPACE(f(n)) is strictly contained in DSPACE(f(n) log(f(n))) [[zooref#hls65|[HLS65]]].

For space constructible f(n), strictly contains [[#dtime|DTIME]](f(n)) [[zooref#hpv77|[HPV77]]].

DSPACE(n) does not equal [[Complexity Zoo:N#np|NP]] (though we have no idea if one contains the other)!

See also: [[Complexity Zoo:N#nspace|NSPACE]](f(n)).

----

===== <span id="dtime" style="color:red">DTIME(f(n))</span>: Deterministic f(n)-Time =====
The class of decision problems solvable by a Turing machine in time <math>O(f(n))</math>. Note that some authors choose to call this class TIME.

Of great relevance to DTIME is the Time Hierarchy Theorem: For any constructible function <math>f(n)</math> greater than <math>n</math>, DTIME(<math>f(n)</math>) is strictly contained in DTIME(<math>f(n) \log(f(n)) \log\log(f(n))</math>) [[zooref#hs65|[HS65]]]. As a corollary, {{zcls|p|p}} &sub; {{zcls|e|exp}}.

For any space constructible <math>f(n)</math>, DTIME(<math>f(n)</math>) is strictly contained in DSPACE(<math>f(n)</math>) [[zooref#hpv77|[HPV77]]].

Also, DTIME(<math>n</math>) is strictly contained in [[Complexity Zoo:N#ntime|NTIME(<math>n</math>)]] [[zooref#pps83|[PPS+83]]] (this result does not work for arbitrary <math>f(n)</math>).

For any constructible superpolynomial <math>f(n)</math>, DTIME(<math>f(n)</math>) with [[Complexity Zoo:P#pp|PP]] oracle is not in [[Complexity Zoo:P#ppoly|P/poly]] (see [[zooref#all96|[All96]]]).

----

===== <span id="dtisp" style="color:red">DTISP(t(n),s(n))</span>: Simultaneous t(n)-Time and s(n)-Space =====
The class of decision problems solvable by a Turing machine that uses time O(t(n)) and space O(s(n)) simultaneously.

Thus [[Complexity Zoo:S#sc|SC]] = DTISP(poly,polylog) for example.

Defined in [[zooref#nis92|[Nis92]]], where it was also shown that for all space-constructible s(n)=&Omega;(log n), [[Complexity Zoo:B#bpspace|BPSPACE(s(n))]] is contained in DTISP(2<sup>O(s(n))</sup>,s<sup>2</sup>(n)).

----

===== <span id="dynfo" style="color:red">Dyn-FO</span>: Dynamic [[Complexity Zoo:F#fo|FO]] =====
The class of <i>dynamic</i> problems solvable using first-order predicates.

Basically what this means is that an algorithm maintains some polynomial-size data structure (say a graph), and receives a sequence of updates (add this edge, delete that one, etc.).  For each update, it computes a new value for the data structure in [[Complexity Zoo:F#fo|FO]] -- that is, for each bit of the data structure, there is an [[Complexity Zoo:F#fo|FO]] function representing the new value of that bit, which takes as input both the update and the previous value of the data structure.  At the end the algorithm needs to answer some question (i.e. is the graph connected?).

See [[zooref#hi02|[HI02]]] for more information, and a complete problem for Dyn-FO.

See also [[#dynthc0|Dyn-ThC<sup>0</sup>]].

----
===== <span id="dynthc0" style="color:red">Dyn-ThC<sup>0</sup></span>: Dynamic Threshold Circuits =====
Same as [[#dynfo|Dyn-FO]], except that now updates are computed via constant-depth predicates that have "COUNT" available, in addition to AND, OR, and NOT -- so it's a uniform version of [[Complexity Zoo:T#tc0|TC<sup>0</sup>]] rather than of [[Complexity Zoo:A#ac0|AC<sup>0</sup>]].

See [[zooref#hi02|[HI02]]] for more information.