Una red dirigida acíclica de puertas lógicas booleanas (AND, OR, NOT, etc.) conectadas por cables que calcula funciones booleanas desde bits de entrada a bits de salida; se utiliza como modelo de computación no uniforme en el que cada tamaño de entrada tiene su propio circuito.

Principio

Calcular una función booleana componiendo pequeñas primitivas lógicas fijas en un grafo acíclico de modo que las salidas sean combinaciones booleanas deterministas de las entradas; la complejidad se mide por tamaño (número de puertas) y profundidad (camino más largo).

Demostración

Para una longitud de entrada fija n, diseñar un circuito que calcule la paridad combinando los bits de entrada por pares en un árbol binario equilibrado de puertas XOR; analizar la profundidad como O(log n) y el tamaño como O(n).

Aplicación incorrecta

Tratar un único circuito como una descripción algorítmica uniforme para todos los tamaños de entrada sin especificar una familia de circuitos, o suponer fan-in/fan-out arbitrario sin coste, lo que conduce a afirmaciones engañosas sobre complejidad.

Consecuencia

Proporciona un modelo concreto, basado en tamaño y profundidad, para clases de complejidad no uniformes (por ejemplo P/poly) y perspectivas sobre realizabilidad hardware; la profundidad se relaciona con el tiempo paralelo y el tamaño con el coste de recursos.

Inversión

Un modelo secuencial y uniforme como la máquina de Turing o la RAM describe un único procedimiento algorítmico que funciona para todos los tamaños de entrada mediante un programa finito, invirtiendo la perspectiva no uniforme por tamaño de circuito.

Límite

Asume lógica booleana y aciclicidad; excluye circuitos secuenciales con memoria a menos que se amplíen con registros; los modelos de coste varían según fan-in, fan-out y tipos de puertas; no captura puertas probabilísticas o cuánticas salvo extensión explícita.

Tensión semántica

Cercano a fórmulas (circuitos en forma de árbol) y programas de decisión; la tensión surge entre familias de circuitos (no uniformes) y modelos algorítmicos uniformes donde una única descripción debe escalar con el tamaño de entrada.

Síntesis

Una composición estática y acíclica de puertas booleanas parametrizada por el tamaño de entrada que mapea de manera determinista bits de entrada a salidas; medir tamaño y profundidad aporta visión sobre recursos no uniformes y paralelos en computación.