LOGCFL

Un article de Wikipédia, l'encyclopédie libre.
Ceci est la version actuelle de cette page, en date du 31 octobre 2018 à 13:34 et modifiée en dernier par Roll-Morton (discuter | contributions). L'URL présente est un lien permanent vers cette version.
(diff) ← Version précédente | Voir la version actuelle (diff) | Version suivante → (diff)

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 | modifier le code]

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

Problèmes dans LOGCFL[modifier | modifier le code]

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 | modifier le code]

  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 )
Ce document provient de « https://fr.wikipedia.org/w/index.php?title=LOGCFL&oldid=153546373 ».