Incomputational complexity theory,DLOGTIME is thecomplexity class of allcomputational problems solvable in alogarithmic amount ofcomputation time on a deterministicTuring machine. It must be defined on arandom-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 includes problems relating to verifying the length of the input,[1] for example the problem "Is the input of even length?", which can be solved in logarithmic time usingbinary search.
DLOGTIME-uniformity is important incircuit complexity.[1][2]
| P ≟ NP | Thistheoretical computer science–related article is astub. You can help Wikipedia byexpanding it. |