LOGCFL

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

Exemple

Cette section est vide, insuffisamment détaillée ou incomplète. Votre aide est la bienvenue ! Comment faire ?

Problèmes dans LOGCFL

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.

Notes et références

  1. ↑ (en) « Complexity Zoo:L - Complexity Zoo » [archive du ], sur complexityzoo.uwaterloo.ca via Internet Archive (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 )