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 ⊆ AC¹.

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].

(en) « Complexity Zoo:L - Complexity Zoo », sur complexityzoo.uwaterloo.ca (consulté le 30 octobre 2018)
Patrick W. Dymond et Stephen A. Cook, « Complexity theory of parallel time and hardware », Information and Computation, vol. 80, n^o 3,‎ 1^er mars 1989, p. 205–226 (ISSN 0890-5401, DOI 10.1016/0890-5401(89)90009-6, lire en ligne, consulté le 30 octobre 2018)

Cet article est issu de wikipedia. Text licence: CC BY-SA 4.0, Des conditions supplémentaires peuvent s’appliquer aux fichiers multimédias.