Problème de l'évaluation d'un circuit

Exemple d'un circuit avec deux entrées 1 et 0. La sortie vaut 1 (cliquer sur l'image pour voir l'animation qui calcule la sortie).

En informatique théorique, plus précisément en théorie de la complexité, le problème de l'évaluation d'un circuit (appelé CIRCUIT VALUE PROBLEM, CVP, CIRCUIT EVALUATION PROBLEM ou CIRCUIT-EVAL en anglais) est le problème de décision qui consiste à calculer la sortie d'un circuit booléen sur des entrées données.

P-complétude

Richard E. Ladner a démontré en 1975 que ce problème est complet pour la classe P. La démonstration de la P-dureté par rapport à une réduction en espace logarithmique se réalise comme suit. On encode l'exécution de longueur polynomiale d'une machine de Turing à l'aide d'un circuit booléen. La P-complétude de CVP joue le même rôle pour les problèmes ouverts P = LOGSPACE ou P = NLOGSPACE que le problème SAT (voir théorème de Cook) pour le problème ouvert P = NP.

Restrictions

Le problème reste P-complet pour des circuits booléens planaires et des circuits booléens monotones (pas de portes NON, que des portes ET et OU). Il est dans NC (plus précisément dans LOGCFL) pour des circuits booléens planaires et monotones,.

Si par contre, on considère une formule booléenne au lieu d'un circuit booléen général (autrement dit, si le circuit booléen est un arbre), le problème est plus simple. En 1977, Nancy A. Lynch a démontré que le problème est dans LOGSPACE. En 1987, Samuel R. Buss montre un résultat plus précis : le problème est complet pour la classe ALOGTIME (ALOGTIME est égale à NC1 (voir NC) avec une condition d'uniformité DLOGTIME, cette classe est incluse dans LOGSPACE).

Notes et références

  1. 1 2 « Computational Complexity: A Modern Approach / Sanjeev Arora and Boaz Barak », sur theory.cs.princeton.edu (consulté le ), p. 119, Th. 6.30
  2. ↑ Richard E. Ladner, « The circuit value problem is log space complete for P », ACM SIGACT News, vol. 7, no 1,‎ , p. 18–20 (ISSN 0163-5700, DOI 10.1145/990518.990519, lire en ligne, consulté le )
  3. ↑ (en) « Cours à l'université de Cornell - The circuit value problem »,
  4. ↑ Leslie M. Goldschlager, « The monotone and planar circuit value problems are log space complete for P », ACM SIGACT News, vol. 9, no 2,‎ , p. 25–29 (ISSN 0163-5700, DOI 10.1145/1008354.1008356, lire en ligne, consulté le )
  5. ↑ 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 )
  6. ↑ Honghua Yang, « An NC algorithm for the general planar monotone circuit value problem », Proceedings of the Third IEEE Symposium on Parallel and Distributed Processing,‎ , p. 196–203 (DOI 10.1109/SPDP.1991.218279, lire en ligne, consulté le )
  7. ↑ Nancy Lynch, « Log Space Recognition and Translation of Parenthesis Languages », Journal of the ACM (JACM), vol. 24, no 4,‎ , p. 583–590 (ISSN 0004-5411, DOI 10.1145/322033.322037, lire en ligne, consulté le )
  8. ↑ Samuel R. Buss, « The Boolean formula value problem is in ALOGTIME », sur www.math.ucsd.edu, (consulté le )
  9. ↑ (en) « On uniformity within NC1 », Journal of Computer and System Sciences, vol. 41, no 3,‎ , p. 274–306 (ISSN 0022-0000, DOI 10.1016/0022-0000(90)90022-D, lire en ligne, consulté le )