Circuito booleano

Un circuito particular actúa únicamente sobre entradas de tamaño fijo. Sin embargo, los lenguajes formales (las representaciones basadas en cadenas de caracteres de los problemas de decisión ) contienen cadenas de distintas longitudes, por lo que un solo circuito no puede capturarlos completamente (a diferencia del modelo de máquina de Turing, en el que una sola máquina de Turing describe completamente un lenguaje). En cambio, un lenguaje se representa mediante una familia de circuitos . Una familia de circuitos es una lista infinita de circuitos.${\displaystyle (C_{0},C_{1},C_{2},...)}$, dónde${\displaystyle C_{n}}$tiene${\displaystyle n}$variables de entrada. Se dice que una familia de circuitos decide un lenguaje.${\displaystyle L}$si, para cada cadena${\displaystyle w}$,${\displaystyle w}$está en el idioma${\displaystyle L}$si y solo si${\displaystyle C_{n}(w)=1}$, dónde${\displaystyle n}$es la longitud de${\displaystyle w}$En otras palabras, un lenguaje es el conjunto de cadenas que, al aplicarse a los circuitos correspondientes a sus longitudes, dan como resultado 1. ^{[ 2 ] : 354}

En los circuitos booleanos se pueden definir varias medidas importantes de complejidad , como la profundidad del circuito, su tamaño y el número de alternancias entre las compuertas AND y OR. Por ejemplo, la complejidad de tamaño de un circuito booleano se define por el número de compuertas que contiene.

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, que requiere relativamente pocas operaciones secuenciales en una máquina de Turing ) también tiene una complejidad de circuito pequeña (es decir, que requiere relativamente pocas operaciones booleanas). Formalmente, se puede demostrar que si un lenguaje está en${\displaystyle {\mathsf {TIEMPO}}(t(n))}$, dónde${\displaystyle t}$es una función${\displaystyle t:\mathbb {N} \to \mathbb {N} }$, entonces tiene complejidad de tamaño de circuito${\displaystyle O(t^{2}(n))}$.

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${\displaystyle {\mathsf {TIEMPO}}(t(n))}$tener complejidad de circuito${\displaystyle O(t^{2}(n))}$que P${\displaystyle \subseteq }$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, la inclusión es propia (es decir, P${\displaystyle \subsetneq }$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${\displaystyle \neq }$NP. ^{[ 3 ] : 286} P/poly también ayuda a investigar propiedades de la jerarquía polinómica . Por ejemplo, si NP ⊆ P/poly, entonces PH se reduce a${\displaystyle \Sigma _{2}^{\mathsf {P}}}$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 interesante característica de que puede definirse equivalentemente como la clase de lenguajes reconocidos por una máquina de Turing de tiempo polinomial con una función de asesoramiento acotada polinomialmente .

Dos subclases de P/poly que poseen propiedades interesantes por derecho propio son NC y AC . Estas clases se definen no solo en términos del tamaño de su 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 al 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 un tamaño polinomial, sino también a tener una profundidad polilogarítmica . La clase AC se define de manera similar a NC, sin embargo, se permite que las compuertas tengan un fan-in ilimitado (es decir, las compuertas AND y OR pueden aplicarse a más de dos bits). NC es una clase importante porque resulta que representa la clase de lenguajes que poseen algoritmos paralelos eficientes .

El problema del valor del circuito —el problema de calcular la salida de un circuito booleano dado sobre 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 lo resuelva.

Los circuitos lógicos son la representación física de operaciones lógicas simples, AND, OR y NOT (y sus combinaciones, como biestables no secuenciales o redes de circuitos), que forman una estructura matemática conocida como álgebra booleana . Son completos en el sentido de que pueden ejecutar cualquier algoritmo determinista. Sin embargo, esto no es todo. En el mundo físico también encontramos aleatoriedad, especialmente en sistemas pequeños regidos por efectos de cuantización, descritos por la teoría de la mecánica cuántica . Los circuitos lógicos no pueden generar aleatoriedad, y en ese sentido forman un conjunto lógico incompleto. La solución a esto se encuentra en añadir un generador de bits aleatorios ad hoc a las redes lógicas o a las computadoras, como en la máquina de Turing probabilística . Un trabajo reciente ^{[ 4 ]} ha introducido el concepto teórico de un circuito lógico inherentemente aleatorio llamado biestable aleatorio , que completa el conjunto. Este circuito incorpora aleatoriedad de forma conveniente y es interoperable con circuitos lógicos booleanos deterministas. Sin embargo, aún se desconoce una estructura algebraica equivalente al álgebra booleana y los métodos asociados de construcción y reducción de circuitos para el conjunto extendido.