Problème de l'évaluation d'un circuit
# 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 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 à $NC^1$ (voir NC) avec une condition d'uniformité DLOGTIME, cette classe est incluse dans LOGSPACE).

