In
computational complexity
In computer science, the computational complexity or simply complexity of an algorithm is the amount of resources required to run it. Particular focus is given to computation time (generally measured by the number of needed elementary operations ...
, the logarithmic time hierarchy (LH) is the
complexity class
In computational complexity theory, a complexity class is a set (mathematics), set of computational problems "of related resource-based computational complexity, complexity". The two most commonly analyzed resources are time complexity, time and s ...
of all
computational problem
In theoretical computer science, a computational problem is one that asks for a solution in terms of an algorithm. For example, the problem of factoring
:"Given a positive integer ''n'', find a nontrivial prime factor of ''n''."
is a computati ...
s solvable in a
logarithmic Logarithmic can refer to:
* Logarithm, a transcendental function in mathematics
* Logarithmic scale, the use of the logarithmic function to describe measurements
* Logarithmic spiral,
* Logarithmic growth
* Logarithmic distribution, a discrete pro ...
amount of
computation time
In theoretical 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 p ...
on an
alternating Turing machine
In computational complexity theory, an alternating Turing machine (ATM) is a non-deterministic Turing machine (NTM) with a rule for accepting computations that generalizes the rules used in the definition of the complexity classes NP and co-NP ...
with a bounded number of alternations. It is a particular case of a
bounded alternating Turing machine hierarchy. It is equal to
FO and to FO-uniform
AC0.
The
th level of the logarithmic time hierarchy is the set of languages recognised by alternating Turing machines in logarithmic time with
random access
Random access (also called direct access) is the ability to access an arbitrary element of a sequence in equal time or any datum from a population of addressable elements roughly as easily and efficiently as any other, no matter how many elemen ...
and
alternations, beginning with an
existential state. LH is the union of all levels.
References
Complexity classes
{{Comp-sci-theory-stub