LH (complexity) (original) (raw)

From Wikipedia, the free encyclopedia

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 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.

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