# DLOGTIME

Jump to navigation
Jump to search

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-uniformity is important in circuit complexity.^{[1]}^{[2]}

## References[edit]

- ^
^{a}^{b}Johnson, David S. (1990), "A catalog of complexity classes",*Handbook of theoretical computer science, Vol. A*, Elsevier, Amsterdam, pp. 67–161, MR 1127168. See in particular p. 140. **^**Allender, Eric; Gore, Vivek (1993), "On strong separations from AC^{0}",*Advances in computational complexity theory (New Brunswick, NJ, 1990)*, DIMACS Ser. Discrete Math. Theoret. Comput. Sci.,**13**, Amer. Math. Soc., Providence, RI, pp. 21–37, MR 1255326. See in particular p. 23.

P ≟ NP | This theoretical computer science–related article is a stub. You can help Wikipedia by expanding it. |