Circuit booléen

Un circuit booléen est un graphe orienté acyclique (DAG) fini connexe dont les feuilles sont les entrées et l'unique racine est la sortie. Les sommets sont les portes, généralement des portes ET, OU et NON[1]. On peut évaluer la valeur de sortie récursivement à partir des feuilles : pour une porte "ET" par exemple, si les entrées sont positives la sortie sera positive sinon la sortie est négative.

Une formule de la logique propositionnelle est un cas particulier de circuit booléen qui est un arbre.

On peut aussi modéliser des circuits par des programmes straight-line[2] : ce sont des programmes sans conditionnelles et sans boucles. Par exemple, le circuit booléen de l'illustration est équivalent au programme straight-line suivant, en appelant x₁ et x₂ les entrées, et en introduisant les variables y₁, y₂, y₃ pour les trois portes logique :

y₁ := x₁ ou x₂

y₂ := non x₂

y₃ := y₁ et y₂

Les circuits classiques décident des langages codés en binaire : le premier bit du mot est la première entrée, etc. Le mot est accepté si et seulement si la sortie du circuit est vrai. Comme un circuit ne permet de reconnaître que des mots de même tailles, on parle généralement de famille de circuits ${\displaystyle (C_{n})_{n}}$, où ${\displaystyle C_{n}}$ reconnaît les mots du langage de taille ${\displaystyle n}$. Un modèle comme celui-ci, où il y a un circuit différent pour chaque taille de l'entrée, est dit « non uniforme ».

Les circuits booléens, à l'instar d'autres modèles de calcul comme les machines de Turing, permettent de définir des classes de complexité. Une classe de complexité regroupent des problèmes algorithmiques selon l'utilisation de ressources (temps, mémoire, etc.) qu'il faut pour les décider. Les classes présentées ici, qui reposent sur les circuits, définissent des classes de complexité où les ressources sont :

• la taille du circuit, i.e. le nombre de portes logique et d'entrées qu'il y a dans un circuit (par exemple, le circuit en illustration est de taille 5 (2 entrées + 3 portes logique) ;
• la profondeur du circuit

Voici des exemples de classes de complexité que l'on peut définir avec des circuits.

• La classe P/poly est la classe des langages pouvant être reconnu par des circuits de tailles polynomiales.
• La classe AC⁰, la classe des langages pouvant être reconnu par des circuits de tailles polynomiales et de profondeur constante (avec degré entrant non borné)
• La hiérarchie NC, des langages pouvant être reconnu par des circuits de tailles polynomiales et de profondeur polylogarithmique (avec degré entrant borné)
• La hiérarchie AC, la classe des langages pouvant être reconnu par des circuits de tailles polynomiales et de profondeur polylogarithmique (avec degré entrant non borné)
• La hiérarchie TC, la classe des langages pouvant être reconnu par des circuits avec des portes ET, OU, MAJORITE, de tailles polynomiales et de profondeur polylogarithmique (avec degré entrant non borné)

Le problème de l'évaluation d'un circuit, qui consiste à décider la sortie du circuit sur des entrées données, est un problème P-complet.