vignette|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
Catégorie:Problème algorithmique