DLOGTIME
From Wikipedia, the free encyclopedia
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.
