LOGCFL
classe de complexité
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.
Exemple
modifier
Cette section est vide, insuffisamment détaillée ou incomplète. Votre aide est la bienvenue ! Comment faire ?
Problèmes dans LOGCFL
modifier Cette section est vide, insuffisamment détaillée ou incomplète. Votre aide est la bienvenue ! Comment faire ?
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
modifier- (en) « Complexity Zoo:L - Complexity Zoo », sur complexityzoo.uwaterloo.ca (consulté le )
- 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 )
