Circuito booleano

En la teoría de la complejidad computacional y la complejidad de circuitos , un circuito booleano es un modelo matemático para circuitos lógicos digitales combinacionales . Un lenguaje formal puede decidirse por 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 AND y OR binarias y puertas NOT unarias , o estar completamente descrito por puertas NAND binarias . Cada puerta corresponde a alguna función booleana que toma una cantidad fija de bits como entrada y genera un solo bit como salida.

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 abanico de salida , los fallos , el consumo de energía y la variabilidad del retardo de propagación .

Definición formal

Al dar una definición formal de los circuitos booleanos, Vollmer comienza definiendo una base como un conjunto B de funciones booleanas, correspondientes a las puertas permitidas en el modelo de circuito. Un circuito booleano sobre una base B , con n entradas y m salidas, se define entonces como un grafo 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 las 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 salida 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 { AND , OR , NOT }, que es funcionalmente completo , es decir, a partir del cual se pueden construir todas las demás funciones booleanas.

Complejidad computacional

Fondo

Un circuito particular actúa solo sobre entradas de tamaño fijo. Sin embargo, los lenguajes formales (las representaciones basadas en cadenas de los problemas de decisión ) contienen cadenas de diferentes longitudes, por lo que los lenguajes no pueden ser capturados completamente por un solo circuito (en contraste con el modelo de máquina de Turing, en el que un lenguaje es descrito completamente por una sola máquina de Turing). En cambio, un lenguaje se representa mediante 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 lenguaje si, para cada cadena , está en el lenguaje si y solo si , donde es la longitud de . En otras palabras, un lenguaje es el conjunto de cadenas que, cuando se aplican a los circuitos correspondientes a sus longitudes, evalúan a 1. ^[2]^{: 354} $(C_{0},C_{1},C_{2},...)$ $Estilo de visualización C_{n}$ ${\estilo de visualización n}$ ${\estilo de visualización L}$ ${\estilo de visualización w}$ ${\estilo de visualización w}$ ${\estilo de visualización L}$ $C_{n}(w)=1$ ${\estilo de visualización n}$ ${\estilo de visualización w}$

Medidas de complejidad

Se pueden definir varias medidas de complejidad importantes en los circuitos booleanos, entre ellas la profundidad del circuito, el tamaño del circuito y la cantidad de alternancias entre puertas AND y puertas OR. Por ejemplo, la complejidad del tamaño de un circuito booleano es la cantidad de puertas del circuito.

Existe una conexión natural entre la complejidad del tamaño del circuito y la complejidad temporal . ^[2]^{: 355} Intuitivamente, un lenguaje con una complejidad temporal pequeña (es decir, requiere relativamente pocas operaciones secuenciales en una máquina de Turing ), también tiene una complejidad de circuito pequeña (es decir, requiere relativamente pocas operaciones booleanas). Formalmente, se puede demostrar que si un lenguaje está en , donde es una función , entonces tiene una complejidad de circuito . ${\mathsf {TIEMPO}}(t(n))$ ${\estilo de visualización t}$ $t:\mathbb {N} \to \mathbb {N}$ $Estilo de visualización O(t^{2}(n))}$

Clases de complejidad

Varias clases de complejidad importantes se definen en términos de circuitos booleanos. La más general de ellas es P/poly , el conjunto de lenguajes que son decidibles por familias de circuitos de tamaño polinomial. Se deduce directamente del hecho de que los lenguajes en tienen complejidad de circuito que P P/poly. En otras palabras, cualquier problema que pueda ser calculado en tiempo polinomial por una máquina de Turing determinista también puede ser calculado por una familia de circuitos de tamaño polinomial. Además, es el caso de que la inclusión es adecuada (es decir, P P/poly) porque hay problemas indecidibles que están en P/poly. 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 lenguaje 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 polinomial con una función de asesoramiento acotada por polinomios . ${\mathsf {TIEMPO}}(t(n))$ $Estilo de visualización O(t^{2}(n))}$ $\subseteq$ $\subsetneq$ ${\estilo de visualización \neq}$ $\Sigma _{2}^{\mathsf {P}}$

Dos subclases de P/poly que tienen propiedades interesantes por derecho propio son NC y AC . Estas clases se definen no solo 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 de la ruta dirigida más larga desde un nodo de entrada hasta el nodo de salida. La clase NC es el conjunto de lenguajes que pueden ser resueltos por 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 un abanico de entrada ilimitado (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 .

Evaluación de circuitos

El problema del valor del circuito (el problema de calcular la salida de un circuito booleano dado en una cadena de entrada dada ) es un problema de decisión P-completo . ^[3]^{: 119} Por lo tanto, este problema se considera "inherentemente secuencial" en el sentido de que probablemente no exista un algoritmo eficiente y altamente paralelo que resuelva el problema.

Lo completo

Los circuitos lógicos son representaciones físicas de operaciones lógicas simples, AND, OR y NOT (y sus combinaciones, como flip-flops no secuenciales o redes de circuitos), 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. El remedio para eso se encuentra en agregar un generador de bits aleatorios ad-hoc a las redes lógicas o las computadoras, como en la máquina de Turing probabilística . Un trabajo reciente ^[4] ha introducido un concepto teórico de un circuito lógico inherentemente aleatorio llamado flip-flop aleatorio , que completa el conjunto. Empaca convenientemente la 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.

Véase también

Notas al pie

^ ab Vollmer, Heribert (1999). Introducción a la complejidad de circuitos . Berlín: Springer. ISBN 3-540-64310-9.
^ ab Sipser, Michael (2006). Introducción a la teoría de la computación (2.ª ed.). EE. UU.: Thomson Course Technology. ISBN 978-0-534-95097-2.
^ ab Arora, Sanjeev; Barak, Boaz (2009). Complejidad computacional: un enfoque moderno . Cambridge University Press. ISBN 978-0-521-42426-4.
^ Stipčević, Mario; Batelić, Mateja (2022). "Consideraciones de entropía en circuitos mejorados para una computadora de pulso aleatorio de inspiración biológica". Scientific Reports . 12 : 115. arXiv : 1908.04779 . doi : 10.1038/s41598-021-04177-9 .