LH (complexity) explained

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

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.

Notes and References

  1. Book: . Descriptive Complexity. Descriptive Complexity . 1999 . Springer . 85.

This article is licensed under the GNU Free Documentation License. It uses material from the Wikipedia article "LH (complexity)".

Except where otherwise indicated, Everything.Explained.Today is © Copyright 2009-2024, A B Cryer, All Rights Reserved. Cookie policy.