Circuito (informática)

Modelo de cálculo

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.

Definición formal

Un circuito es un triplete , donde ${\displaystyle (M,L,G)}$

• ${\displaystyle M}$es un conjunto de valores,
• ${\displaystyle 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 ${\displaystyle M^{i}}$ ${\displaystyle M}$ ${\displaystyle i}$ ${\displaystyle i}$
• ${\displaystyle G}$es un gráfico acíclico dirigido etiquetado con etiquetas de . ${\displaystyle 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 ${\displaystyle g}$ ${\displaystyle i}$ ${\displaystyle g}$ ${\displaystyle \ell }$ ${\displaystyle L}$ ${\displaystyle \ell }$ ${\displaystyle M^{i}.}$

Terminología

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. ${\displaystyle g}$ ${\displaystyle h}$ ${\displaystyle G}$ ${\displaystyle h}$ ${\displaystyle g}$ ${\displaystyle k}$ ${\displaystyle 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. ${\displaystyle g}$ ${\displaystyle G}$ ${\displaystyle g}$

El nivel ${\displaystyle 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. ${\displaystyle i}$ ${\displaystyle i}$ ${\displaystyle i+1}$

Evaluación

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

${\displaystyle V(g)={\begin{cases}l&{\text{if }}g{\text{ is an input}}\\l(V(g_{1}),\dotsc ,V(g_{i}))&{\text{otherwise,}}\end{cases}}}$

donde cada uno es un padre de . ${\displaystyle g_{j}}$ ${\displaystyle g}$

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

Circuitos como funciones

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 . ${\displaystyle M}$ ${\displaystyle n}$ ${\displaystyle M^{n}}$ ${\displaystyle M}$ ${\displaystyle (C_{n})_{n\in \mathbb {N} }}$ ${\displaystyle C_{n}}$ ${\displaystyle n}$ ${\displaystyle M^{*}}$ ${\displaystyle 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 size(n)}$ ${\displaystyle n}$

Complejidad y problemas algorítmicos

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.

Véase también

• 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

Referencias

• 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.