Difference between revisions of "Complexity Zoo:D"

From Complexity Zoo
Jump to navigation Jump to search
 
(10 intermediate revisions by 7 users not shown)
Line 6: Line 6:
  
 
----
 
----
 +
 
===== <span id="dcfl" style="color:red">DCFL</span>: Deterministic [[Complexity Zoo:C#cfl|CFL]] =====
 
===== <span id="dcfl" style="color:red">DCFL</span>: Deterministic [[Complexity Zoo:C#cfl|CFL]] =====
 
The class of languages accepted by deterministic pushdown automata.
 
The class of languages accepted by deterministic pushdown automata.
Line 15: Line 16:
 
===== <span id="delta2p" style="color:red">&#916;<sub>2</sub>P</span>: [[Complexity Zoo:P#p|P]] With [[Complexity Zoo:N#np|NP]] Oracle =====
 
===== <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.
 
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]].
 
Contains [[Complexity Zoo:B#bh|BH]].
Line 45: Line 48:
 
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.
 
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]]].
+
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]]].
 
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]]].
 
[[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.
  
 
----
 
----
Line 59: Line 64:
  
 
----
 
----
 +
 +
===== <span id="distributionph" style="color:red">DistributionPH</span>: Distribution [[Complexity Zoo:P#ph|PH]] =====
 +
 +
Not to be confused with DistPH, as in [[Complexity Zoo:D#distnp|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.
 +
<br> If the proofs are allowed to be correlated, then the hierarchy collapses to just two levels as for [[Complexity Zoo#Q:qeph|QEPH]].
 +
 +
Defined in [[zooref#gy24|[GY24]]] and shown to collapse to the standard definition of [[Complexity Zoo:P#ph|PH]].
 +
 +
----
 +
 
===== <span id="disnp" style="color:red">DisNP</span>: Disjoint [[Complexity Zoo:N#np|NP]] Pairs =====
 
===== <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.
 
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.
Line 80: Line 97:
 
----
 
----
  
===== <span id="dp" style="color:red">DP</span>: Difference Polynomial-Time =====
+
===== <span id="dp" style="color:red">DP</span> or <span id="Dp" style="color:red">D<sup>p</sup></span>: Difference Polynomial-Time =====
 
DP = [[Complexity Zoo:B#bh|BH]]<sub>2</sub>, the second level of the Boolean hierarchy.
 
DP = [[Complexity Zoo:B#bh|BH]]<sub>2</sub>, 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 &#916;<sub>2</sub>P.
 +
 +
Complete problems: Exact-Clique, SAT-UNSAT, etc.
  
 
Defined in [[zooref#py84|[PY84]]].
 
Defined in [[zooref#py84|[PY84]]].
Line 93: Line 116:
  
 
[[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#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 =====
 
===== <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.
 
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.

Latest revision as of 09:14, 24 September 2024

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, PEXP.

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.