LH (complexité)
En informatique théorique, plus précisément en théorie de la complexité, la hiérarchie en temps logarithmique (LH) est la classe de complexité des problèmes de décision qui décidés par des machines de Turing alternantes, avec accès direct, en temps logarithmique et avec un nombre borné d'alternations. LH correspond à la logique du premier ordre en complexité descriptive et est égale à AC0 uniforme selon la logique du premier ordre[1].
Notes et références
- (en) N. Immerman, Descriptive complexity, Springer, , p. 85.
Liens externes
Cet article est issu de wikipedia. Text licence: CC BY-SA 4.0, Des conditions supplémentaires peuvent s’appliquer aux fichiers multimédias.