DLOGTIME
Encyclopedia
DLOGTIME is the complexity class
of all computational problem
s 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.
Complexity class
In computational complexity theory, a complexity class is a set of problems of related resource-based complexity. A typical complexity class has a definition of the form:...
of all computational problem
Computational problem
In theoretical computer science, a computational problem is a mathematical object representing a collection of questions that computers might want to solve. For example, the problem of factoring...
s solvable in a logarithmic
Logarithmic growth
In mathematics, logarithmic growth describes a phenomenon whose size or cost can be described as a logarithm function of some input. e.g. y = C log . Note that any logarithm base can be used, since one can be converted to another by a fixed constant...
amount of computation time on a deterministic Turing machine
Turing machine
A Turing machine is a theoretical device that manipulates symbols on a strip of tape according to a table of rules. Despite its simplicity, a Turing machine can be adapted to simulate the logic of any computer algorithm, and is particularly useful in explaining the functions of a CPU inside a...
. It is the smallest nontrivial class using the resource of deterministic time. It must be defined on a random-access Turing machine
Random-access Turing machine
In computational complexity, a field of computer science, random-access Turing machines are an extension of Turing machines used to speak about small complexity classes, especially for classes using logarithmic time, like DLOGTIME and the Logarithmic Hierarchy....
, since otherwise the machine does not have time to read the entire input tape.
DLOGTIME-uniformity is important in circuit complexity
Circuit complexity
In theoretical computer science, circuit complexity is a branch of computational complexity theory in which Boolean functions are classified according to the size or depth of Boolean circuits that compute them....
.
The problem of testing the length of the input string can be solved in DLOGTIME, by binary searching for possible input sizes.