LH (complexité)

Un article de Wikipédia, l'encyclopédie libre.

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]

  1. ↑ (en) N. Immerman, Descriptive complexity, Springer, , p. 85.

Liens externes[modifier | modifier le code]

(en) La classe LH sur le Complexity Zoo

Ce document provient de « https://fr.wikipedia.org/w/index.php?title=LH_(complexité)&oldid=143181746 ».