In
computational complexity theory
In theoretical computer science and mathematics, computational complexity theory focuses on classifying computational problems according to their resource usage, and relating these classes to each other. A computational problem is a task solved by ...
, DLOGTIME is the
complexity class
In computational complexity theory, a complexity class is a set of computational problems of related resource-based complexity. The two most commonly analyzed resources are time and memory.
In general, a complexity class is defined in terms of ...
of all
computational problem
In theoretical computer science, a computational problem is a problem that may be solved by an algorithm. For example, the problem of factoring
:"Given a positive integer ''n'', find a nontrivial prime factor of ''n''."
is a computational probl ...
s solvable in a
logarithmic amount of
computation time
In computer science, the time complexity is the computational complexity that describes the amount of computer time it takes to run an algorithm. Time complexity is commonly estimated by counting the number of elementary operations performed by t ...
on a deterministic
Turing machine
A Turing machine is a mathematical model of computation describing an abstract machine that manipulates symbols on a strip of tape according to a table of rules. Despite the model's simplicity, it is capable of implementing any computer algori ...
. It must be defined on a
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 logarith ...
, 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.
[. See in particula]
p. 140
Examples
DLOGTIME includes problems relating to verifying the length of the input,
for example the problem "''Is the input of even length?''", which can be solved in logarithmic time using
binary search
In computer science, binary search, also known as half-interval search, logarithmic search, or binary chop, is a search algorithm that finds the position of a target value within a sorted array. Binary search compares the target value to the m ...
.
Applications
DLOGTIME-
uniformity is important in
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 the Boolean circuits that compute them. A related notion is the circui ...
.
[. See in particula]
p. 23
References
Complexity classes
{{Comp-sci-theory-stub