Complexity Zoo:D
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
D#P - DCFL - Δ2P - δ-BPP - δ-RP - DET - DiffAC0 - DisNP - DistNP - DP - DQC1 - DQP - DSPACE(f(n)) - DTIME(f(n)) - DTISP(t(n),s(n)) - Dyn-FO - Dyn-ThC0
D#P: Alternate Name for P#P
DCFL: Deterministic CFL
The class of languages accepted by deterministic pushdown automata.
Defined in [GG66], where it was also shown that DCFL is strictly contained in CFL, contained in UCFL, and strictly contains REG. The inclusion in UCFL is also strict.
Δ2P: P With NP Oracle
A level of PH, the polynomial hierarchy.
One Δ2P-complete problem: Given a Boolean formula, does the lexicographically last satisfying assignment end with a 1? [Kre88]
Contains BH.
There exists an oracle relative to which Δ2P is not contained in PP [Bei94].
There exists another oracle relative to which Δ2P is contained in P/poly [BGS75], and indeed has linear-size circuits [Wil85].
There exists an oracle B for which BPPB is exponentially more powerful than Δ2PB [KV96].
If P = NP, then any polynomial-size circuit C can be learned in Δ2P with C oracle [Aar06].
δ-BPP: δ-Semi-Random BPP
Same as 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 [δ,1-δ], conditioned on all previous bits.
So clearly 0-BPP = P and 1/2-BPP = BPP.
It turns out that, for any δ>0, δ-BPP = BPP [VV85], [Zuc91].
δ-RP: δ-Semi-Random RP
Same as δ-BPP, but for RP instead of BPP.
For any δ>0, δ-RP = RP [VV85].
DET: Determinant
The class of decision problems reducible in L to the problem of computing the determinant of an n-by-n matrix of n-bit integers.
Defined in [Coo85]. (Cook used NC1 reductions in his definition)
Contained in NC2, and contains NL and PL [BCP83].
Graph isomorphism is hard for DET under L-reductions [Tor00].
The corresponding function class turns out to be equal to GapL (see refs at GapL), that is, the determinant of integer matrices is GapL-complete.
DiffAC0: Difference #AC0
The class of functions from {0,1}n to integers expressible as the difference of two #AC0 functions.
Equals GapAC0 under logspace uniformity [ABL98].
DistributionPH: Distribution PH
Not to be confused with DistPH, as in DistNP.
A middle-ground between classical and quantum proofs. Provers send (independent) probability distributions, or mixed states. After all proofs are sent, the verifier draws one sample from each proof.
If the proofs are allowed to be correlated, then the hierarchy collapses to just two levels as for QEPH.
Defined in [GY24] and shown to collapse to the standard definition of PH.
DisNP: Disjoint NP Pairs
The class of pairs (A,B), where A and B are 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 [Raz94]. On the other hand, there exists an oracle relative to which DisNP does not have a complete pair [GSS+03].
If P does not equal UP, then DisNP contains pairs not separated by any set in P [GS88]. On the other hand, there exists an oracle relative to which P does not equal NP but still DisNP does not contain any P-inseparable pairs [HS92].
DistNP: Distributional NP
(also called (NP,P-computable) or RNP)
A distributional problem consists of a decision problem A, and a probability distribution μ over problem instances.
(A,μ) is in DistNP if A is in NP, and μ is P-computable (meaning that its cumulative density function can be evaluated in polynomial time).
DistNP has complete problems [Lev86] (see also [Gur87]), although unlike for NP this is not immediate.
Any DistNP-complete problem is also complete for (NP,P-samplable) [IL90].
DP or Dp: Difference Polynomial-Time
DP = BH2, the second level of the Boolean hierarchy.
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 Δ2P.
Complete problems: Exact-Clique, SAT-UNSAT, etc.
Defined in [PY84].
DQC1: Deterministic Quantum Computing with 1 Clean Bit
The class of problems solvable by a 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 BQP by first initializing the computer to the all-0 state.
[ASV00] showed that if DQC1 = BQP, something other than gate-by-gate simulation will be needed to show this.
[SJ08] showed that approximating the Jones polynomial at a fifth root of unity for the trace closure of a braid is complete for DQC1.
DQP: Dynamical Quantum Polynomial-Time
The class of decision problems solvable by a BQP machine with oracle access to a dynamical simulator. 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 [Aar05] for a full definition.
There it is also shown that SZK is contained in DQP.
Contains BQP, and is contained in EXP [Aar05].
There exists an oracle relative to which DQP does not contain NP [Aar05].
DSPACE(f(n)): 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))) [HLS65].
For space constructible f(n), strictly contains DTIME(f(n)) [HPV77].
DSPACE(n) does not equal NP (though we have no idea if one contains the other)!
See also: NSPACE(f(n)).
DTIME(f(n)): Deterministic f(n)-Time
The class of decision problems solvable by a Turing machine in time . Note that some authors choose to call this class TIME.
Of great relevance to DTIME is the Time Hierarchy Theorem: For any constructible function greater than , DTIME() is strictly contained in DTIME() [HS65]. As a corollary, P ⊂ EXP.
For any space constructible , DTIME() is strictly contained in DSPACE() [HPV77].
Also, DTIME() is strictly contained in NTIME() [PPS+83] (this result does not work for arbitrary ).
For any constructible superpolynomial , DTIME() with PP oracle is not in P/poly (see [All96]).
DTISP(t(n),s(n)): 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 SC = DTISP(poly,polylog) for example.
Defined in [Nis92], where it was also shown that for all space-constructible s(n)=Ω(log n), BPSPACE(s(n)) is contained in DTISP(2O(s(n)),s2(n)).
Dyn-FO: Dynamic FO
The class of dynamic 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 FO -- that is, for each bit of the data structure, there is an 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 [HI02] for more information, and a complete problem for Dyn-FO.
See also Dyn-ThC0.
Dyn-ThC0: Dynamic Threshold Circuits
Same as 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 TC0 rather than of AC0.
See [HI02] for more information.