Réseau acyclique dirigé de portes logiques booléennes (ET, OU, NON, etc.) reliées par des fils qui calcule des fonctions booléennes des bits d'entrée vers les bits de sortie ; utilisé comme modèle non uniforme de calcul où chaque taille d'entrée a son propre circuit.

Principe

Calculer une fonction booléenne en composant des primitives logiques fixes dans un graphe acyclique de sorte que les sorties soient des combinaisons booléennes déterministes des entrées ; la complexité se mesure par la taille (nombre de portes) et la profondeur (plus long chemin).

Démonstration

Pour une longueur d'entrée n fixée, concevoir un circuit qui calcule la parité en XORant les bits d'entrée par paires dans un arbre binaire équilibré de portes XOR ; analyser la profondeur en O(log n) et la taille en O(n).

Mauvaise application

Traiter un seul circuit comme une description algorithmique uniforme pour toutes les tailles d'entrée sans spécifier une famille de circuits, ou supposer une fan-in/fan-out arbitraire sans coût, ce qui conduit à des affirmations trompeuses sur la complexité.

Conséquence

Fournit un modèle concret, basé sur la taille et la profondeur, pour les classes de complexité non uniformes (par ex. P/poly) et des perspectives sur la réalisabilité matérielle ; la profondeur se rapporte au temps parallèle tandis que la taille se rapporte au coût des ressources.

Inversion

Un modèle séquentiel et uniforme comme la machine de Turing ou la RAM décrit une unique procédure algorithmique valide pour toutes les tailles d'entrée via un programme fini, inversant le point de vue non uniforme par taille de circuit.

Limite

Suppose la logique booléenne et l'acyclicité ; exclut les circuits séquentiels avec mémoire sauf s'ils sont augmentés de registres ; les modèles de coût varient selon la fan-in, fan-out et le type de portes ; ne capture pas les portes probabilistes ou quantiques sauf extension explicite.

Tension sémantique

Proche des formules (circuits en forme d'arbre) et des programmes de branchement ; la tension apparaît entre familles de circuits (non uniformes) et modèles algorithmiques uniformes où une seule description doit s'étendre avec la taille d'entrée.

Synthèse

Composition statique et acyclique de portes booléennes paramétrée par la taille d'entrée qui mappe de façon déterministe les bits d'entrée aux sorties ; mesurer la taille et la profondeur éclaire les ressources non uniformes et parallèles en calcul.