Menu
Home Explore People Places Arts History Plants & Animals Science Life & Culture Technology
On this page
LH (complexity)
Set of the computational problems solvable in a logarithmic amount of computation time on an alternating Turing machine with a bounded number of alternations

In computational complexity, the logarithmic time hierarchy (LH) is the complexity class of all computational problems solvable in a logarithmic amount of computation time on an alternating Turing machine 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 i {\displaystyle i} th level of the logarithmic time hierarchy is the set of languages recognised by alternating Turing machines in logarithmic time with random access and i − 1 {\displaystyle i-1} alternations, beginning with an existential state. LH is the union of all levels.

We don't have any images related to LH (complexity) yet.
We don't have any YouTube videos related to LH (complexity) yet.
We don't have any PDF documents related to LH (complexity) yet.
We don't have any Books related to LH (complexity) yet.
We don't have any archived web articles related to LH (complexity) yet.

References

  1. Neil Immerman (1999). Descriptive Complexity. Springer. p. 85. /wiki/Neil_Immerman