DLOGTIME

Uses your system voice; voice and rate in settings.

Q5205561Snapshot

≈ 5 min read

Names in other languages

  • العربيةDLOGTIME
  • DeutschDLOGTIME
  • EnglishDLOGTIME
  • FrançaisDLOGTIME
  • ItalianoDLOGTIME
  • NederlandsDLOGTIME
  • PortuguêsDLOGTIME
  • 中文DLOGTIME

Article bodies are English and are not machine-translated. A name in another language is not a translation of the article.

In computational complexity theory, DLOGTIME is the complexity class of all computational problems solvable in a logarithmic amount of computation time on a deterministic Turing machine. It must be defined on a random-access Turing machine, since otherwise the input tape is longer than the range of cells that can be accessed by the machine. It is a very weak model of time complexity: no random-access Turing machine with a smaller deterministic time bound can access the whole input. DLOGTIME machines are rarely used as-is.

Instead, they are usually used as part of a theoretical construct for studying reducibility. They cannot be used to produce output that is longer than logarithmic length. However, they can be used to indirectly produce such an output, in the following sense: Given any log-length binary address, it produces the corresponding bit of the output. Since a polynomial-sized integer has logarithmic-length binary representation, this is possible in DLOGTIME.

In computational complexity theory, DLOGTIME is the complexity class of all computational problems solvable in a logarithmic amount of computation time on a deterministic Turing machine. It must be defined on a random-access Turing machine, since otherwise the input tape is longer than the range of cells that can be accessed by the machine. It is a very weak model of time complexity: no random-access Turing machine with a smaller deterministic time bound can access the whole input. DLOGTIME machines are rarely used as-is.

Instead, they are usually used as part of a theoretical construct for studying reducibility. They cannot be used to produce output that is longer than logarithmic length. However, they can be used to indirectly produce such an output, in the following sense: Given any log-length binary address, it produces the corresponding bit of the output. Since a polynomial-sized integer has logarithmic-length binary representation, this is possible in DLOGTIME.

Examples

DLOGTIME can solve some problems relating to verifying the length of the input, such as "Is the input of even length?", which can be solved in logarithmic time using binary search. More generally, for any p \geq 1 and integer k , it can decide if |x| \equiv k \mod p . It does so by first converting |x| to its binary representation on the work tape, using binary search, then going through the binary representation bit by bit, keeping track of its mod-p status using the lookup table stored in the Turing machine's state-transition table.

The family of DLOGTIME-decidable problems is closed under finite union, finite intersection, and negation. L_f=\left\{\langle x, i, c\rangle \mid f(x)_i=c\right\} is DLOGTIME-decidable. This allows definition of DLOGTIME-computation of Boolean circuit families. Note: Because DLOGTIME machine only has enough time to check O(\log n) \ll n entries in the input, we usually must restrict the input to the function f to only unary input. That is, the input to the function can only be \epsilon, 1, 11, 111, \dots , to avoid trivial failures.

Circuit complexity

DLOGTIME-uniformity is used in circuit complexity. A Boolean circuit family C_0, C_1, \dots is DLOGTIME-uniform iff the function 1^n \mapsto desc(C_n) is implicitly DLOGTIME computable, where desc(C_n) is a description of the circuit. It is very weak in the following sense: \mathsf{AC}^0_0 \subsetneq \mathsf{DLOGTIME} \subsetneq \mathsf{AC}^0_2 , where AC consists of DLOGTIME-uniform unlimited fan-in circuits of depth between 0 and 2.

Also, \mathsf{DLOGTIME} is not comparable with \mathsf{AC}^0_1 , meaning that neither one of them contains the other (XOR is in DLOGTIME, AND and OR are in \mathsf{AC}^0_1 ). The assumption of DLOGTIME-uniformity is important, since otherwise even a \mathsf{AC}^0_0 circuit family may encode a non-computable sequence in the choice of their indices. To show \mathsf{DLOGTIME} \subset \mathsf{AC}^0_2 , note that the machine can perform only O( \log n) random-access reads, each returning one input bit.

Call the transcript of such a computation the ordered list \left(\left(p_1, b_1\right), \ldots,\left(p_{c \log n}, b_{c \log n}\right)\right) of the positions it probes and the bits it observes. Since each p_t is determined by the previously read bits, there are only 2^{c\log n} = \mathsf{poly}(n) possible transcripts. For each accepting transcript, build an AND gate that checks exactly those c \log n literals \mapsto "position p_j contains bit \mathrm{b}_j ". Wire all these gates into one big OR. That yields a \mathsf{AC}_2^0 circuit.

It is clear, by construction, that this construction is \mathsf{DLOGTIME} -uniform.

References

Text derived from https://en.wikipedia.org/w/index.php?oldid=1333819509 under CC BY-SA 4.0; modifications have been made.

Provenance

snapshot dlogtime-593031-8b77f035411ad5f1 · hash 8b77f035411ad5f1bb07c3bdbd9116e788ec4515cb7a62e06f2d1c76a826964d · captured 1768859786.0 · version history

Cite this page as: encyclopegia.org, “DLOGTIME”, snapshot dlogtime-593031-8b77f035411ad5f1. https://encyclopegia.org/a/dlogtime

Sources cited in this revision

2 named source(s) extracted from the cited revision. A source with no author is shown by its publication; nothing is invented.