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.^[1]

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.

Definition

Consider a deterministic Turing machine with the following tapes:^[1]: 140

• The read-only input tape.
• The address tape, which it can read and write.
• The work tape, which it can read and write.

The machine is only allowed to read from the input tape thus: It transitions to a "read" state, then at the next time-step, it receives the bit on the input tape, at the index according to the binary address on the address tape.

DLOGTIME is the class of decision problems solvable by such a machine in ${\displaystyle O(\log n)}$ time where ${\displaystyle n}$ is the length of the input.

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 ${\displaystyle p\geq 1}$ and integer ${\displaystyle k}$, it can decide if ${\displaystyle |x|\equiv k\mod p}$. It does so by first converting ${\displaystyle |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.

Transducer

The DLOGTIME machine may be supplied with an output tape, though in that case, it would have only enough time to output ${\displaystyle O(\log n)}$ bits. This allows it to perform sequence transduction, from a length ${\displaystyle n}$ sequence to a length ${\displaystyle O(\log n)}$ sequence.

In order to perform transductions into longer sequences, we may define implicit transduction by the standard trick, also used in Log-space reduction.

A function ${\displaystyle f:2^{*}\to 2^{*}}$ is implicitly DLOGTIME computable iff:^[1]: 140

• It is polynomially bounded: There exists some ${\displaystyle c>0}$ such that ${\displaystyle f(x)\leq |x|^{c}}$ for all ${\displaystyle x\in 2^{*}}$.
• ${\displaystyle 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 ${\displaystyle O(\log n)\ll n}$ entries in the input, we usually must restrict the input to the function ${\displaystyle f}$ to only unary input. That is, the input to the function can only be ${\displaystyle \epsilon ,1,11,111,\dots }$, to avoid trivial failures.

Circuit complexity

DLOGTIME-uniformity is used in circuit complexity. A boolean circuit family ${\displaystyle C_{0},C_{1},\dots }$ is DLOGTIME-uniform iff the function ${\displaystyle 1^{n}\mapsto desc(C_{n})}$ is implicitly DLOGTIME computable, where ${\displaystyle desc(C_{n})}$ is a description of the circuit.^[1][2]

It is very weak in the following sense: ${\displaystyle {\mathsf {AC}}_{0}^{0}\subsetneq {\mathsf {DLOGTIME}}\subsetneq {\mathsf {AC}}_{2}^{0}}$, where AC consists of DLOGTIME-uniform unlimited fan-in circuits of depth between 0 and 2. Also, ${\displaystyle {\mathsf {DLOGTIME}}}$ is not comparable with ${\displaystyle {\mathsf {AC}}_{1}^{0}}$, meaning that neither one of them contains the other (XOR is in DLOGTIME, AND and OR are in ${\displaystyle {\mathsf {AC}}_{1}^{0}}$).^[1] The assumption of DLOGTIME-uniformity is important, since otherwise even a ${\displaystyle {\mathsf {AC}}_{0}^{0}}$ circuit family may encode a non-computable sequence in the choice of their indices.

To show ${\displaystyle {\mathsf {DLOGTIME}}\subset {\mathsf {AC}}_{2}^{0}}$, note that the machine can perform only ${\displaystyle O(\log n)}$ random-access reads, each returning one input bit. Call the transcript of such a computation the ordered list$${\displaystyle \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 ${\displaystyle p_{t}}$ is determined by the previously read bits, there are only ${\displaystyle 2^{c\log n}={\mathsf {poly}}(n)}$ possible transcripts. For each accepting transcript, build an AND gate that checks exactly those ${\displaystyle c\log n}$ literals ${\displaystyle \mapsto }$ "position ${\displaystyle p_{j}}$ contains bit ${\displaystyle \mathrm {b} _{j}}$". Wire all these gates into one big OR. That yields a ${\displaystyle {\mathsf {AC}}_{2}^{0}}$ circuit. It is clear, by construction, that this construction is ${\displaystyle {\mathsf {DLOGTIME}}}$-uniform.

References

1. Leeuwen, Jan (1990-09-12). Algorithms and Complexity. Elsevier. ISBN 978-0-444-88071-0.
2. Allender, Eric; Gore, Vivek (1993), "On strong separations from AC⁰", Advances in computational complexity theory (New Brunswick, NJ, 1990), DIMACS Ser. Discrete Math. Theoret. Comput. Sci., vol. 13, Amer. Math. Soc., Providence, RI, pp. 21–37, MR 1255326. See in particular p. 23.