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.

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[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 )
  • icône décorative Portail de l'informatique théorique