Circuit booléen

Un article de Wikipédia, l'encyclopédie libre.
Aller à : navigation, rechercher

En théorie de la complexité, un circuit booléen est un modèle de calcul constitué de portes (fonctions logiques) reliées entre elles.

Un circuit booléen peut être utilisé pour reconnaître un langage formel, c'est-à-dire décider si un mot appartient ou non à un langage particulier. Les caractéristiques des circuits qui reconnaissent un langage permettent de définir (ou redéfinir) des classes de complexité.

Les circuits booléens sont un modèle utilisé en génie informatique notamment pour la conception des unités arithmétiques et logiques et en informatique théorique notamment pour établir des bornes inférieures.

Définition formelle[modifier | modifier le code]

Un circuit booléen est un graphe orienté acyclique fini (DAG) 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. 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 négative.

Famille de circuits et non-uniformité[modifier | modifier le code]

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 (C_n)_n, où C_n reconnaît les mot du langage de taille n. Un modèle comme celui-ci, où l'on change de méthode selon la taille de l'entrée, est appelé non-uniforme.

Classes de complexité[modifier | modifier le code]

Les classes suivantes sont des classes de circuits typiques :

  • La classe P/poly est la classe des langages pouvant être reconnu par des circuits de tailles polynomiales.
  • La classe NC, est la classe des pouvant être reconnu par des circuits de tailles polynomiales et de profondeur polylogarithmique.

Bornes inférieures[modifier | modifier le code]

Un autre intérêt des circuits booléens est leur simplicité (en comparaison aux machines de Turing) qui permet de prouver certaines bornes inférieures du type : les circuits reconnaissant tel langage doivent être de taille au moins f(n). Ce genre de borne permet de différencier certaines classes.

Bibliographie[modifier | modifier le code]

Liens externes[modifier | modifier le code]

Notes et références[modifier | modifier le code]