LH (complexité)
From Wikipedia (Fr) - Reading time: 1 min
Cet article est une ébauche concernant l’informatique théorique.
Vous pouvez partager vos connaissances en l’améliorant (comment ?) selon les recommandations des projets correspondants.
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[modifier | modifier le code]
- (en) N. Immerman, Descriptive complexity, Springer, , p. 85.
Liens externes[modifier | modifier le code]
Licensed under CC BY-SA 3.0 | Source: https://fr.wikipedia.org/wiki/LH_(complexité)6 views | ↧ Download this article as ZWI file
EncycloReader
is supported by the 
KSF