LOGCFL

En théorie de la complexité, LOGCFL (pour Logarithmically Reducible to context-free language en anglais[1]) désigne la classe des problèmes réductibles en espace logarithmique à un langage hors contexte. On a NL ⊆ LOGCFL ⊆ AC1.

Problèmes dans LOGCFL

Le problème d'évaluation d'un circuit booléen planaire et monotone (pas de portes NON) est dans LOGCFL[2].

Notes et références
  1. (en) « Complexity Zoo:L - Complexity Zoo », sur complexityzoo.uwaterloo.ca (consulté le )
  2. Patrick W. Dymond et Stephen A. Cook, « Complexity theory of parallel time and hardware », Information and Computation, vol. 80, no 3,‎ , p. 205–226 (ISSN 0890-5401, DOI 10.1016/0890-5401(89)90009-6, lire en ligne, consulté le )
  • Portail de l'informatique théorique
Cet article est issu de Wikipedia. Le texte est sous licence Creative Commons - Attribution - Partage dans les Mêmes. Des conditions supplémentaires peuvent s'appliquer aux fichiers multimédias.