LH (複雑さ)

計算複雑性において、対数時間階層( LH )は、交代回数が制限された交代チューリングマシン上で対数的な計算時間で解けるすべての計算問題の計算複雑性クラスである。これは、制限付き交代チューリングマシン階層の特殊なケースである。これは、 FOおよび FO-uniform AC ⁰に等しい。^[1]

対数時間階層の 番目のレベルは、存在状態から始まり、ランダムアクセスと交代を伴う対数時間で交代チューリングマシンによって認識される言語の集合です。LHはすべてのレベルの和集合です。 ${\displaystyle i}$${\displaystyle i-1}$