LH (complexity)

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.[1]

The th level of the logarithmic time hierarchy is the set of languages recognised by alternating Turing machines in logarithmic time with random access and alternations, beginning with an existential state. LH is the union of all levels.

References

  1. Neil Immerman (1999). Descriptive Complexity. Springer. p. 85.
This article is issued from Wikipedia. The text is licensed under Creative Commons - Attribution - Sharealike. Additional terms may apply for the media files.