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

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^[1] 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.

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

P-complétude

Richard E. Ladner a démontré en 1975^[2] que ce problème est complet pour la classe P^[1]. 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^[3]. 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)^[4]. Il est dans NC (plus précisément dans LOGCFL) pour des circuits booléens planaires et monotones^[5],[6].

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^[7]. En 1987, Samuel R. Buss montre un résultat plus précis : le problème est complet pour la classe ALOGTIME^[8] (ALOGTIME est égale à NC¹ (voir NC) avec une condition d'uniformité DLOGTIME^[9], cette classe est incluse dans LOGSPACE).