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 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 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 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 pr ...
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 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 (more precisely and more generally 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 othe ...
and
alternations, beginning with an
existential state. LH is the union of all levels.
References
Complexity classes
{{Comp-sci-theory-stub