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 - Δ₂P - δ-BPP - δ-RP - DET - DiffAC⁰ - DisNP - DistNP - DP - DQC1 - DQP - DSPACE(f(n)) - DTIME(f(n)) - DTISP(t(n),s(n)) - Dyn-FO - Dyn-ThC⁰

---

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.

---

Δ₂P: P With NP Oracle

A level of PH, the polynomial hierarchy.

One Δ₂P-complete problem: Given a Boolean formula, is the lexicographically last satisfying assignment start with a 1? [Kre88]

Contains BH.

There exists an oracle relative to which Δ₂P is not contained in PP [Bei94].

There exists another oracle relative to which Δ₂P is contained in P/poly [BGS75], and indeed has linear-size circuits [Wil85].

There exists an oracle B for which BPP^B is exponentially more powerful than Δ₂P^B [KV96].

If P = NP, then any polynomial-size circuit C can be learned in Δ₂P 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].

Contained in NC², and contains NL and PL [BCP83].

Graph isomorphism is hard for DET under L-reductions [Tor00].

---

DiffAC⁰: Difference #AC⁰

The class of functions from {0,1}ⁿ to integers expressible as the difference of two #AC⁰ functions.

Equals GapAC⁰ under logspace uniformity [ABL98].

---

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: Difference Polynomial-Time

DP = BH₂, the second level of the Boolean hierarchy.

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.

---

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 $O(f(n))$. Note that some authors choose to call this class TIME.

Of great relevance to DTIME is the Time Hierarchy Theorem: For any constructible function $f(n)$ greater than $n$, DTIME($f(n)$) is strictly contained in DTIME($f(n)\log(f(n))\log \log(f(n))$) [HS65]. As a corollary, P ⊂ EXP.

For any space constructible $f(n)$, DTIME($f(n)$) is strictly contained in DSPACE($f(n)$) [HPV77].

Also, DTIME($n$) is strictly contained in NTIME($n$) [PPS+83] (this result does not work for arbitrary $f(n)$).

For any constructible superpolynomial $f(n)$, DTIME($f(n)$) 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(2^O(s(n)),s²(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-ThC⁰.

---

Dyn-ThC⁰: 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 TC⁰ rather than of AC⁰.

See [HI02] for more information.