LH (complejidad)

En complejidad computacional , la jerarquía de tiempo logarítmico ( LH ) es la clase de complejidad de todos los problemas computacionales resolubles en una cantidad logarítmica de tiempo de computación en una máquina de Turing alternante con un número limitado de alternancias. Es un caso particular de una jerarquía de máquina ^de Turing alternante limitada . Es igual a FO y a FO-uniform AC ^{0. [ 1} ]

El${\displaystyle i}$El nivel n de la jerarquía de tiempo logarítmico es el conjunto de lenguajes reconocidos por máquinas de Turing alternas en tiempo logarítmico con acceso aleatorio y${\displaystyle i-1}$alternancias, comenzando con un estado existencial . LH es la unión de todos los niveles.