DLOGTIME

 ( Complexity Classes ) 

• 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 $O(\backslash log\; n)$ time where $n$ is the length of the input.

More generally, for any $p\; \backslash geq\; 1$ and integer $k$, it can decide if $|x|\; \backslash equiv\; k\; \backslash 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.

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 $f:\; 2^*\; \backslash to\; 2^*$ is implicitly DLOGTIME computable iff:

• It is polynomially bounded: There exists some $c\; >\; 0$ such that $f(x)\; \backslash leq\; |x|^c$ for all $x\backslash in\; 2^*$.
• $L\_f=\backslash left\backslash \{\backslash langle\; x,\; i,\; c\backslash rangle\; \backslash mid\; f(x)\_i=c\backslash right\backslash \}$ is DLOGTIME-decidable.

Note: Because DLOGTIME machine only has enough time to check $O(\backslash log\; n)\; \backslash 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 $\backslash epsilon,\; 1,\; 11,\; 111,\; \backslash dots$, to avoid trivial failures.