Class Description

LH: Logarithmic Time Hierarchy

A logarithmic-time alternating Turing machine is an alternating Turing machine that halts in logarithmic time, assuming the model of computation in which the machine has a special query tape on which it can write the binary integer i and receive the ith bit of the input string as a response, thus allowing any bit of an input string of length n to be read in time logarithmic in n. (There are other ways of defining the model of computation; see [RV97].)

The ith level of the Logarithmic Time Hierarchy is the set of languages recognised by a logarithmic-time alternating Turing machine making at most i alternations, beginning with existential state. LH is the union of all levels of the hierarchy.

LH equals AC0 and FO [Imm98].

Linked From

No class.