LH (complexidade)

Na ciência da computação teórica , especificamente na teoria da complexidade , a hierarquia logarítmica do tempo (LH) é a classe de complexidade dos problemas de decisão que são decididos por máquinas de Turing alternadas com acesso direto, em tempo logarítmico e com um número limitado de alternâncias. LH corresponde à lógica de primeira ordem em complexidade descritiva e é igual a AC 0 uniforme de acordo com a lógica de primeira ordem.

Notas e referências

  1. (en) N. Immerman, complexidade descritiva , Springer,1999, p.  85.

links externos

(fr) A classe LH no Zoo Complexity