LH (complexity)

Logarithmic Hierarchy 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 alternation. It is a special case of hierarchy of bounded alternating Turing machine. It is equal to FO and to FO-uniform AC0^[1].

The $i$ th level of the Logarithmic Time Hierarchy is the set of languages recognised by alternating Turing machine in logtime with random access and $i-1$ alternation, beginning with existential state. LH is the union of all levels.

References

^ *N. Immerman Descriptive complexity (1999 Springer), page 85.

P ≟ NP

This theoretical computer science–related article is a stub. You can help Wikipedia by expanding it.

[1] *N. Immerman Descriptive complexity (1999 Springer), page 85.

[1]

v t e Complexity classes
Considered feasible	DLOGTIME AC⁰ ACC⁰ TC TC⁰ L SL RL FL 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 TFNP FNP 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