Circuit booléen
En théorie de la complexité, un circuit booléen est un modèle de calcul constitué de portes logiques (fonctions logiques) reliées entre elles. C'est une façon de représenter une fonction booléenne.
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
modifierUn 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 x1 et x2 les entrées, et en introduisant les variables y1, y2, y3 pour les trois portes logiques :
- y1 := x1 ou x2
- y2 := non x2
- y3 := y1 et y2
Famille de circuits et non-uniformité
modifierLes 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êmes tailles, on parle généralement de famille de circuits , où reconnaît les mots du langage de taille . 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 ».
Classes de complexité
modifierLes 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é regroupe 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 logiques) ;
- 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 AC0, 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é)
Taille des circuits
modifierBornes supérieures
modifierLupanov, en 1952, démontre que toute fonction booléenne sur n variables admet un circuit de taille (1 + o(1))2n/n[3].
Bornes inférieures
modifierShanon, en 1949, démontre que pour tout n > 1, il existe une fonction booléenne à n variables qui n'admet pas de circuit de taille 2n/(10n)[4]. 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 . Ce genre de borne permet de différencier certaines classes. Cependant, trouver de bonnes bornes inférieures pour les circuits est considéré comme difficile, et dans certains cas, on peut prouver que les techniques classiques ne peuvent pas fonctionner, c'est le cas des preuves naturelles pour le problème P=NP[5]. Une borne inférieure connue est que la fonction parité n'appartient pas à AC0.
Propriétés
modifierLe 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.
Notes et références
modifier- Sylvain Perifel, Complexité algorithmique, Ellipses, , 432 p. (ISBN 9782729886929, lire en ligne), chap. 5 (« Circuits booléens ») 5.2.1, Définition, p. 134.
- Sanjeev Arora et Boaz Barak, Computational Complexity : A Modern Approach, Cambridge University Press, , 579 p. (ISBN 978-0-521-42426-4 et 0-521-42426-7, lire en ligne), p. 109 Note 6.4
- (en) « Cours sur les tailles de circuits »
- Arora, Sanjeev., Computational Complexity : A Modern Approach, Cambridge University Press, , 579 p. (ISBN 978-0-521-42426-4, 9780511804090 et 0511804091, OCLC 851026159, lire en ligne), Th. 6.21, p. 115
- Timothy Y. Chow, « WHAT IS... a Natural Proof? », Notices of the American Mathematical Society, AMS, vol. 58, no 11, (lire en ligne).
Voir aussi
modifierBibliographie
modifier- (en) Sanjeev Arora et Boaz Barak, Computational Complexity : A Modern Approach, Cambridge University Press, (ISBN 0-521-42426-7), chap. 6 (« Boolean circuits »)
- Sylvain Perifel, Complexité algorithmique, Ellipses, , 432 p. (ISBN 9782729886929, lire en ligne), chap. 5 (« Circuits booléens »)
