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.

Definition

Consider a deterministic Turing machine with the following tapes:

• 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.

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.

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

sequence.

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

is implicitly DLOGTIME computable iff:

• .

• is DLOGTIME-decidable.

This allows definition of DLOGTIME-computation of Boolean circuit families.

, to avoid trivial failures.

Circuit complexity

DLOGTIME-uniformity is used in circuit complexity is a description of the circuit.

, where AC). circuit family may encode a non-computable sequence in the choice of their indices.

-uniform.

References