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 compuertas, 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 de lógica digital . Los circuitos se definen por las compuertas que contienen y los valores que estas pueden producir. Por ejemplo, los valores en un circuito booleano son valores booleanos , y el circuito incluye compuertas de conjunción, disyunción y negación. Los valores en un circuito entero son conjuntos de enteros, y las compuertas calculan la unión, la intersección y el complemento de conjuntos, así como las operaciones aritméticas de suma y multiplicación.

Definición formal

Un circuito es un triplete $(M,L,G)$ , dónde

$M$ es un conjunto de valores,
$L$ es un conjunto de etiquetas de puerta, cada una de las cuales es una función de $M^{i}$ a $M$ para algún entero no negativo $i$ (dónde $i$ representa el número de entradas a la puerta), y
$G$ es un grafo acíclico dirigido etiquetado con etiquetas de $L$ .

Los vértices del grafo se llaman puertas . Para cada puerta $g$ de grado de entrada $i$ , la puerta $g$ puede ser etiquetado por un elemento $\ell$ de $L$ si y solo si $\ell$ se define en $M^{i}.$

Terminología

Las puertas de grado de entrada 0 se llaman entradas u hojas . Las puertas de grado de salida 0 se llaman salidas . Si hay una arista desde la puerta $g$ a la puerta $h$ en el gráfico $G$ entonces $h$ se le llama hijo de $g$ Suponemos que existe un orden en los vértices del grafo, por lo que podemos hablar de la $k$ el hijo de una puerta cuando $k$ es menor o igual al grado de salida de la puerta.

El tamaño de un circuito es el número de nodos de un circuito. La profundidad de una puerta $g$ es la longitud del camino más largo en $G$ comenzando en $g$ hasta una puerta de salida. En particular, las puertas de grado de salida 0 son las únicas puertas de profundidad 1. La profundidad de un circuito es la profundidad máxima de cualquier puerta.

Nivel $i$ es el conjunto de todas las puertas de profundidad $i$ . Un circuito nivelado es un circuito en el que los bordes a las puertas de profundidad $i$ Proviene únicamente de puertas de profundidad $i+1$ o desde las entradas. En otras palabras, los bordes solo existen entre niveles adyacentes del circuito. El ancho de un circuito nivelado es el tamaño máximo de cualquier nivel.

Evaluación

El valor exacto $V(g)$ de una puerta $g$ con grado de entrada $i$ y etiqueta $l$ se define recursivamente para todas las compuertas $g$ .

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

donde cada $g_{j}$ es padre de $g$ .

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

Circuitos como funciones

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

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

Complejidad y problemas algorítmicos

Calcular la salida de un circuito booleano dado con 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 de los circuitos intenta clasificar las funciones booleanas en función del tamaño o la profundidad de los circuitos que pueden calcularlas.

Véase también

Referencias

Vollmer, Heribert (1999). Introducción a la complejidad de los 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, septiembre de 2001): 288–303 . doi : 10.1006/jcss.2001.1768 . ISSN 0022-0000 .