Circuitos booleanos

En la teoría de la complejidad computacional y complejidad de circuitos, un circuito booleano es un modelo matemático para circuitos lógicos digitales combinacionales. Una familia de circuitos booleanos puede decidir un lenguaje formal, un circuito para cada longitud de entrada posible. Los circuitos booleanos también se utilizan como modelo formal para la lógica combinacional en electrónica digital.

Los circuitos booleanos se definen en términos de las compuertas lógicas que contienen. Por ejemplo, un circuito puede contener compuertas AND y OR binarias y compuertas NOT unarias, o estar completamente descrito por compuertas NAND binarias. Cada compuerta 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, <i>fan-out</i>, glitches, consumo de energía y variabilidad de retardo de propagación .

Definición formal editar

Al dar una definición formal de los circuitos booleanos, Vollmer comienza definiendo una base como conjunto B de funciones booleanas, que corresponde a las compuertas permitidas en el modelo de circuito. Un circuito booleano sobre una base B, con n entradas y m salidas, se define 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 salidas.^[1] Los bordes también deben tener algún orden, para distinguir entre diferentes argumentos de la misma función booleana.^[2]

Como un caso especial, una fórmula proposicional o expresión booleana es un circuito booleano con un solo nodo de salida en el que todos los demás nodos tienen fan-out de 1. Por lo tanto, un circuito booleano puede considerarse como una generalización que permite subformulas compartidas y salidas múltiples.

Una base común para los circuitos booleanos es el conjunto { AND, OR, NOT }, que es funcionalmente completo, es decir, a partir de él se pueden construir todas las demás funciones booleanas.

Complejidad computacional editar

Antecedentes editar

Un circuito en particular actúa solo en 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 (en contraste con el modelo de máquina de Turing, en el que un lenguaje se describe completamente por una sola máquina de Turing). En cambio, un lenguaje está representado por una familia de circuitos. Una familia de circuitos es una lista infinita de circuitos. $(C_{0},C_{1},C_{2},...)$ , dónde $C_{n}$ tiene $n$ variables de entrada. Se dice que una familia de circuitos decide un idioma $L$ si, por cada cadena $w$ , $w$ está en el idioma $L$ si y solo si $C_{n}(w)=1$ , dónde $n$ es la longitud de $w$ . 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.^[3]

Medidas de complejidad editar

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 compuertas AND y las compuertas OR. Por ejemplo, la complejidad del tamaño de un circuito booleano es el número de puertas.

Resulta que hay una conexión natural entre la complejidad del tamaño del circuito y la complejidad temporal.^[4] Intuitivamente, un lenguaje con poca complejidad temporal (es decir, que 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 ${\mathsf {TIME}}(t(n))$ , dónde $t$ es una función $t:\mathbb {N} \to \mathbb {N}$ , entonces tiene complejidad de circuito $O(t^{2}(n))$ .

Clases de complejidad. editar

Varias clases de complejidad importantes se definen en términos de circuitos booleanos. El más general de estos es P/poly, el conjunto de lenguajes que son decidibles por las familias de circuitos de tamaño polinómico. Se sigue directamente del hecho de que los lenguajes en ${\mathsf {TIME}}(t(n))$ tienen complejidad de circuito $O(t^{2}(n))$ que P $\subseteq$ P/poly. En otras palabras, cualquier problema que pueda calcularse en tiempo polinómico por una máquina de Turing determinista también puede calcularse por una familia de circuitos de tamaño polinómico. Además, el caso es que la inclusión es adecuada (es decir, PAGS $\subsetneq$ P/poly) porque hay problemas indecidibles en P/poly. P/poly resulta tener una serie de propiedades que lo hacen muy útil en el estudio de las relaciones entre las 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 $\neq$ NP.^[5] P/poly también ayuda a investigar las propiedades de la jerarquía polinómica. Por ejemplo, si NP ⊆ P/poly, entonces PH colapsa a $\Sigma _{2}^{\mathsf {P}}$ .P/poly también tiene la característica interesante de que se puede definir de manera equivalente como la clase de lenguajes reconocidos por una máquina de Turing de tiempo polinomial con una función de asesoramiento delimitada por polinomios.

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 al 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 un tamaño polinómico sino también a tener una profundidad poli-logarítmica . La clase AC se define de manera similar a NC, sin embargo, las compuertas pueden tener un fan-in 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 del circuito editar

El problema del valor del circuito, de calcular la salida de un circuito booleano dado en una cadena de entrada dada, es un problema de decisión P-completo.^[6] 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.

Véase también editar

Notas editar

↑ Vollmer 1999, p. 8.
↑ Vollmer 1999, p. 9.
↑ Sipser, Michael (2006). Introduction to the Theory of Computation (2nd edición). USA: Thomson Course Technology. pp. 354. ISBN 978-0-534-95097-2.
↑ Sipser, Michael (2006). Introduction to the Theory of Computation (2nd edición). USA: Thomson Course Technology. p. 355. ISBN 978-0-534-95097-2.
↑ Arora, Sanjeev; Barak, Boaz (2009). Computational Complexity: A Modern Approach. Cambridge University Press. p. 286. ISBN 978-0-521-42426-4.
↑ Arora, Sanjeev; Barak, Boaz (2009). Computational Complexity: A Modern Approach. Cambridge University Press. p. 119. ISBN 978-0-521-42426-4.

Referencias editar

Vollmer, Heribert (1999). Introduction to Circuit Complexity. Berlin: Springer. ISBN 3-540-64310-9.

Datos: Q837479

[1] Vollmer 1999, p. 8.

[2] Vollmer 1999, p. 9.

[3] Sipser, Michael (2006). Introduction to the Theory of Computation (2nd edición). USA: Thomson Course Technology. pp. 354. ISBN 978-0-534-95097-2.

[4] Sipser, Michael (2006). Introduction to the Theory of Computation (2nd edición). USA: Thomson Course Technology. p. 355. ISBN 978-0-534-95097-2.

[arorabarak-5] Arora, Sanjeev; Barak, Boaz (2009). Computational Complexity: A Modern Approach. Cambridge University Press. p. 286. ISBN 978-0-521-42426-4.

[6] Arora, Sanjeev; Barak, Boaz (2009). Computational Complexity: A Modern Approach. Cambridge University Press. p. 119. ISBN 978-0-521-42426-4.

[1]

[2]

[3]

[4]

[5]

[6]