DLOGTIME

From Wikipedia, the free encyclopedia

You have new messages (last change).

DLOGTIME is the complexity class of all computational problems solvable in a logarithmic amount of computation time on a deterministic Turing machine. It is (?) the smallest nontrivial class using the resource of deterministic time. It must be defined on a random-access Turing machine, since otherwise the machine does not have time to read the entire input tape.

DLOGTIME-uniformity is important in circuit complexity.

The problem of testing the length of the input string can be solved in DLOGTIME, by binary searching for possible input sizes.

Comp Sci logo This computer science-related article is a stub. You can help Wikipedia by expanding it.
Retrieved from "http://en.wikipedia.org../../../d/l/o/DLOGTIME_e3de.html"