En teoría de la complejidad computacional y complejidad de circuitos , un circuito booleano es un modelo matemático para circuitos lógicos digitales combinacionales . Un lenguaje formal puede decidirse mediante una familia de circuitos booleanos, un circuito para cada longitud de entrada posible.
Los circuitos booleanos se definen en términos de las puertas lógicas que contienen. Por ejemplo, un circuito puede contener puertas binarias AND y OR y puertas unarias NOT, o estar descrito completamente mediante puertas binarias NAND . Cada puerta corresponde a alguna función booleana que toma un número fijo de bits como entrada y genera un solo bit.
Los circuitos booleanos proporcionan un modelo para muchos componentes digitales utilizados en ingeniería informática , incluidos multiplexores , sumadores y unidades lógicas aritméticas , pero excluyen la lógica secuencial . Son una abstracción que omite muchos aspectos relevantes para el diseño de circuitos lógicos digitales reales, como la metaestabilidad , el fanout , los fallos , el consumo de energía y la variabilidad del retardo de propagación .
Al dar una definición formal de circuitos booleanos, Vollmer comienza definiendo una base como el conjunto B de funciones booleanas, correspondiente a las puertas permitidas en el modelo de circuito. Un circuito booleano sobre una base B , con n entradas ym salidas, se define entonces como un gráfico acíclico dirigido finito . Cada vértice corresponde a una función base o a una de las entradas, y hay un conjunto de exactamente m nodos que están etiquetados como salidas. [1] : 8 Los bordes también deben tener algún orden, para distinguir entre diferentes argumentos de la misma función booleana. [1] : 9
Como caso especial, una fórmula proposicional o expresión booleana es un circuito booleano con un único nodo de salida en el que todos los demás nodos tienen un abanico de 1. Por lo tanto, un circuito booleano puede considerarse como una generalización que permite subfórmulas compartidas y múltiples salidas. .
Una base común para los circuitos booleanos es el conjunto { Y , O , NO }, que es funcionalmente completo , es decir. mi. a partir del cual se pueden construir todas las demás funciones booleanas.
Un circuito particular actúa sólo sobre entradas de tamaño fijo. Sin embargo, los lenguajes formales (las representaciones basadas en cadenas de problemas de decisión ) contienen cadenas de diferentes longitudes, por lo que los lenguajes no pueden ser capturados completamente por un solo circuito (a diferencia del modelo de la máquina de Turing, en el que un lenguaje se describe completamente mediante un único circuito de Turing). máquina). En cambio, un idioma está representado por una familia de circuitos . Una familia de circuitos es una lista infinita de circuitos , donde tiene variables de entrada. Se dice que una familia de circuitos decide un idioma si, para cada cadena , está en el idioma si y solo si , donde está la longitud de . En otras palabras, un lenguaje es el conjunto de cadenas que, cuando se aplican a los circuitos correspondientes a sus longitudes, se evalúan como 1. [2] : 354
Se pueden definir varias medidas de complejidad importantes en los circuitos booleanos, incluida la profundidad del circuito, el tamaño del circuito y el número de alternancias entre las puertas AND y OR. Por ejemplo, la complejidad del tamaño de un circuito booleano es el número de puertas en el circuito.
Existe una conexión natural entre la complejidad del tamaño del circuito y la complejidad del tiempo . [2] : 355 Intuitivamente, un lenguaje con pequeña complejidad de tiempo (es decir, requiere relativamente pocas operaciones secuenciales en una máquina de Turing ), también tiene una pequeña complejidad de circuito (es decir, requiere relativamente pocas operaciones booleanas). Formalmente, se puede demostrar que si un lenguaje está en , donde hay una función , entonces tiene complejidad de circuito .
Varias clases de complejidad importantes se definen en términos de circuitos booleanos. El más general de ellos es P/poly , el conjunto de lenguajes que pueden decidirse mediante familias de circuitos de tamaño polinomial. Del hecho de que los lenguajes tienen complejidad de circuito se deduce directamente que P P/poly. En otras palabras, cualquier problema que pueda calcularse en tiempo polinomial mediante una máquina de Turing determinista también puede calcularse mediante una familia de circuitos de tamaño polinomial. Además, se da el caso de que la inclusión es adecuada (es decir, P P/poli) porque hay problemas indecidibles que están en P/poli. P/poly resulta tener una serie de propiedades que lo hacen muy útil en el estudio de las relaciones entre clases de complejidad. En particular, es útil para investigar problemas relacionados con P versus NP . Por ejemplo, si hay algún idioma en NP que no está en P/poly, entonces P NP. [3] : 286 P/poly también ayuda a investigar las propiedades de la jerarquía polinomial . Por ejemplo, si NP ⊆ P/poly, entonces PH colapsa a . Una descripción completa de las relaciones entre P/poly y otras clases de complejidad está disponible en " Importancia de P/poly ". P/poly también tiene la característica interesante de que puede definirse de manera equivalente como la clase de lenguajes reconocidos por una máquina de Turing de tiempo polinómico con una función de asesoramiento acotada por un polinomio .
Dos subclases de P/poly que tienen propiedades interesantes por derecho propio son NC y AC . Estas clases se definen no sólo en términos de su tamaño de circuito sino también en términos de su profundidad . La profundidad de un circuito es la longitud del camino dirigido más largo desde un nodo de entrada hasta el nodo de salida. La clase NC es el conjunto de lenguajes que pueden resolverse mediante familias de circuitos que están restringidas no solo a tener tamaño polinomial sino también a tener profundidad polilogarítmica . La clase AC se define de manera similar a NC, sin embargo, se permite que las puertas tengan una entrada ilimitada (es decir, las puertas AND y OR se pueden aplicar a más de dos bits). NC es una clase importante porque resulta que representa la clase de lenguajes que tienen algoritmos paralelos eficientes .
El problema del valor del circuito , el problema de calcular la salida de un circuito booleano determinado en una cadena de entrada determinada , es un problema de decisión P-completa . [3] : 119 Por lo tanto, este problema se considera "intrínsecamente secuencial" en el sentido de que probablemente no exista un algoritmo eficiente y altamente paralelo que resuelva el problema.
Los circuitos lógicos son representaciones físicas de operaciones lógicas simples, Y, O y NO (y sus combinaciones, como flip-flops o redes de circuitos no secuenciales), que forman una estructura matemática conocida como álgebra de Boole . Son completos en el sentido de que pueden realizar cualquier algoritmo determinista. Sin embargo, sucede que esto no es todo lo que hay. En el mundo físico también encontramos aleatoriedad, notable en pequeños sistemas gobernados por efectos de cuantificación, que se describe en la teoría de la Mecánica Cuántica. Los circuitos lógicos no pueden producir ninguna aleatoriedad y, en ese sentido, forman un conjunto lógico incompleto. La solución a esto se encuentra en agregar un generador de bits aleatorios ad-hoc a redes lógicas o computadoras, como en la máquina probabilística de Turing . Un trabajo reciente [4] ha introducido un concepto teórico de un circuito lógico inherentemente aleatorio denominado flip-flop aleatorio , que completa el conjunto. Contiene convenientemente aleatoriedad y es interoperable con circuitos lógicos booleanos deterministas. Sin embargo, aún se desconoce una estructura algebraica equivalente al álgebra de Boole y los métodos asociados de construcción y reducción de circuitos para el conjunto extendido.
