Circuito (informática)

En informática teórica, un circuito es un modelo de computación en el que los valores de entrada pasan por una secuencia de puertas, cada una de las cuales calcula una función. Los circuitos de este tipo proporcionan una generalización de los circuitos booleanos y un modelo matemático para los circuitos lógicos digitales. Los circuitos se definen por las puertas que contienen y los valores que las puertas pueden producir. Por ejemplo, los valores de un circuito booleano son valores booleanos, y el circuito incluye puertas de conjunción, disyunción y negación. Los valores de un circuito entero son conjuntos de números enteros y las puertas calculan la unión de conjuntos, la intersección de conjuntos y el complemento de conjuntos, así como las operaciones aritméticas de suma y multiplicación.

Un circuito es un triplete , donde${\estilo de visualización (M,L,G)}$

• ${\estilo de visualización M}$es un conjunto de valores,
• ${\estilo de visualización L}$es un conjunto de etiquetas de puerta, cada una de las cuales es una función de a para algún entero no negativo (donde representa el número de entradas a la puerta), y$Estilo de visualización M^{i}}$${\estilo de visualización M}$${\estilo de visualización i}$${\estilo de visualización i}$
• ${\estilo de visualización G}$es un gráfico acíclico dirigido etiquetado con etiquetas de .${\estilo de visualización L}$

Los vértices del gráfico se denominan puertas . Para cada puerta de grado de entrada , la puerta puede etiquetarse con un elemento de si y solo si está definido en${\estilo de visualización g}$ ${\estilo de visualización i}$${\estilo de visualización g}$${\displaystyle \ell}$${\estilo de visualización L}$${\displaystyle \ell}$${\displaystyle M^{i}.}$

Las puertas de grado de entrada 0 se denominan entradas o salidas . Las puertas de grado de salida 0 se denominan salidas . Si hay una arista de puerta a puerta en el grafo , entonces se denomina hijo de . Suponemos que hay un orden en los vértices del grafo, por lo que podemos hablar del º hijo de una puerta cuando es menor que el grado de salida de la puerta.${\estilo de visualización g}$${\estilo de visualización h}$${\estilo de visualización G}$${\estilo de visualización h}$${\estilo de visualización g}$${\estilo de visualización k}$${\estilo de visualización k}$

El tamaño de un circuito es el número de nodos de un circuito. La profundidad de una compuerta es la longitud del camino más largo desde el inicio hasta una compuerta de salida. En particular, las compuertas de grado de salida 0 son las únicas compuertas de profundidad 1. La profundidad de un circuito es la profundidad máxima de cualquier compuerta. ${\estilo de visualización g}$${\estilo de visualización G}$${\estilo de visualización g}$

El nivel${\estilo de visualización i}$ es el conjunto de todas las puertas de profundidad . Un circuito nivelado es un circuito en el que las aristas de las puertas de profundidad provienen únicamente de las puertas de profundidad o de las entradas. En otras palabras, las aristas solo existen entre niveles adyacentes del circuito. El ancho de un circuito nivelado es el tamaño máximo de cualquier nivel.${\estilo de visualización i}$${\estilo de visualización i}$${\estilo de visualización i+1}$

El valor exacto de una puerta con grado de entrada y etiqueta se define de forma recursiva para todas las puertas .${\displaystyle V(g)}$${\estilo de visualización g}$${\estilo de visualización i}$${\estilo de visualización l}$${\estilo de visualización g}$

${\displaystyle V(g)={\begin{cases}l&{\text{si }}g{\text{ es una entrada}}\\l(V(g_{1}),\dotsc ,V(g_{i}))&{\text{en caso contrario,}}\end{cases}}}$

donde cada uno es un padre de .$estilo de visualización g_ {j}}$${\estilo de visualización g}$

El valor del circuito es el valor de cada una de las puertas de salida.

Las etiquetas de las hojas también pueden ser variables que toman valores en . Si hay hojas, entonces el circuito puede verse como una función de a . Entonces es habitual considerar una familia de circuitos , una secuencia de circuitos indexados por los números enteros donde el circuito tiene variables. Las familias de circuitos pueden verse así como funciones de a .${\estilo de visualización M}$${\estilo de visualización n}$$Estilo de visualización Mn$${\estilo de visualización M}$${\displaystyle (C_{n})_{n\in \mathbb {N}}}$$Estilo de visualización C_{n}$${\estilo de visualización n}$${\estilo de visualización M^{*}}$${\estilo de visualización M}$

Las nociones de tamaño, profundidad y anchura pueden extenderse naturalmente a familias de funciones, convirtiéndose en funciones de a ; por ejemplo, es el tamaño del circuito n de la familia.${\displaystyle \mathbb {N}}$${\displaystyle \mathbb {N}}$${\displaystyle tamaño(n)}$${\estilo de visualización n}$

Calcular la salida de un circuito booleano dado en una entrada específica es un problema P-completo . Sin embargo, si la entrada es un circuito entero , se desconoce si este problema es decidible .

La complejidad del circuito intenta clasificar las funciones booleanas con respecto al tamaño o la profundidad de los circuitos que pueden calcularlas.

• Complejidad de circuitos aritméticos
• Circuito booleano
• Complejidad del circuito
• Circuitos sobre conjuntos de números naturales
• Las clases de complejidad NC , AC y TC
• Circuito cuántico y BQP

• Vollmer, Heribert (1999). Introducción a la complejidad de circuitos . Berlín: Springer. ISBN 978-3-540-64310-4.
• Yang, Ke (2001). "La evaluación de circuitos enteros es PSPACE-completa". Journal of Computer and System Sciences . 63 (2 de septiembre de 2001): 288–303. doi : 10.1006/jcss.2001.1768 . ISSN  0022-0000.