Circuits booléens et complexité des circuits

Les circuits booléens calculent des fonctions via des réseaux de portes logiques, et la complexité des circuits mesure les problèmes en fonction de la taille et de la profondeur des circuits nécessaires pour les résoudre, offrant une perspective de calcul parallèle et orientée matériel.

Definition

Un circuit booléen est un graphe acyclique dirigé de portes logiques calculant une fonction à partir d'entrées binaires de longueur fixe ; la complexité des circuits étudie le nombre minimal de portes, la profondeur ou d'autres ressources structurelles nécessaires pour calculer une famille donnée de fonctions booléennes.

Scope

Ce sujet aborde les circuits et formules booléens, les mesures de complexité basées sur la taille et la profondeur, les modèles uniformes versus non uniformes, les classes de faible profondeur telles que NC et AC, la relation entre les bornes inférieures des circuits et la séparation des classes de complexité, ainsi que les résultats marquants de bornes inférieures pour les familles de circuits restreintes.

Core questions

• En quoi la vision du calcul par réseau de portes diffère-t-elle des machines séquentielles ?
• Que mesurent la taille et la profondeur des circuits, et comment se rapportent-elles au temps et au parallélisme ?
• Pourquoi les bornes inférieures des circuits constituent-elles une voie vers la séparation des classes de complexité ?
• Quelles bornes inférieures sont connues, et quelles barrières empêchent d'en obtenir de plus fortes ?

Key theories

Non-uniformité et la classe P/poly

Les circuits permettent une machine différente pour chaque longueur d'entrée, donnant la classe non uniforme P/poly qui contient P ; montrer qu'un problème NP-complet ne possède pas de circuits de taille polynomiale séparerait P de NP, motivant ainsi les bornes inférieures des circuits.

Bornes inférieures pour les circuits restreints

Des bornes inférieures fortes sont connues pour des familles limitées, telles que la taille exponentielle requise pour les circuits de profondeur constante calculant la parité, même si les bornes inférieures pour les circuits généraux restent hors de portée.

Clinical relevance

Les circuits constituent le modèle naturel du matériel numérique, de sorte que la complexité des circuits éclaire la conception des puces et les limites du calcul parallèle ; les classes de faible profondeur permettent de caractériser ce qui peut être calculé rapidement avec de nombreux processeurs, et les bornes inférieures des circuits représentent une stratégie principale dans l'effort à long terme pour résoudre des questions telles que P versus NP.

History

Shannon a établi le lien entre l'algèbre de Boole et les circuits de commutation en 1937, et la complexité des circuits a mûri en tant que discipline dans les années 1980 lorsque Furst, Saxe, Sipser et d'autres ont prouvé des bornes inférieures de profondeur constante pour la parité, et que Razborov et Smolensky ont développé des méthodes algébriques, avant que la barrière des preuves naturelles ne révèle pourquoi les bornes inférieures générales sont si insaisissables.

Key figures

• Claude Shannon
• Alexander Razborov
• Andrew Yao
• Roman Smolensky

Seminal works

• aroraBarak2009
• vollmer1999

Frequently asked questions

En quoi les circuits diffèrent-ils des machines de Turing ?

Une machine de Turing est un dispositif unique traitant des entrées de toutes tailles étape par étape, tandis qu'un circuit est un réseau fixe de portes pour une longueur d'entrée donnée, avec un circuit distinct pour chaque longueur. Cette non-uniformité fait des circuits un modèle naturel du matériel et du calcul parallèle, et elle peut exprimer des choses qu'aucune machine uniforme unique ne peut faire.

Pourquoi les chercheurs s'intéressent-ils aux bornes inférieures des circuits ?

Prouver qu'un problème dans NP nécessite de très grands circuits séparerait les classes de complexité et pourrait résoudre P versus NP. Des bornes inférieures sont connues pour des familles de circuits restreintes, mais leur extension aux circuits généraux est bloquée par des barrières formelles, ce qui en fait l'un des défis ouverts les plus profonds dans le domaine.