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

The $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$ alternations, beginning with an existential state. LH is the union of all levels.

References

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.

[1] Neil Immerman (1999). Descriptive Complexity. Springer. p. 85.

Important complexity classes
Considered feasible	DLOGTIME AC⁰ ACC⁰ TC⁰ L SL RL NL NL-complete NC SC CC P P-complete ZPP RP BPP BQP APX FP
Suspected infeasible	UP NP NP-complete NP-hard co-NP co-NP-complete AM QMA PH ⊕P PP #P #P-complete IP PSPACE PSPACE-complete
Considered infeasible	EXPTIME NEXPTIME EXPSPACE 2-EXPTIME ELEMENTARY PR R RE ALL
Class hierarchies	Polynomial hierarchy Exponential hierarchy Grzegorczyk hierarchy Arithmetical hierarchy Boolean hierarchy
Families of classes	DTIME NTIME DSPACE NSPACE Probabilistically checkable proof Interactive proof system
List of complexity classes