Circuito (informática)

Modelo de computacion

En informática teórica, un circuito es un modelo de cálculo en el que los valores de entrada pasan a través de 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 circuitos lógicos digitales. Los circuitos están definidos por las puertas que contienen y los valores que las puertas pueden producir. Por ejemplo, los valores en un circuito booleano son valores booleanos y el circuito incluye puertas de conjunción, disyunción y negación. Los valores en un circuito entero son conjuntos de números enteros y las compuertas 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.

Definicion formal

Un circuito es un triple , 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 hasta 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 llaman puertas . Para cada puerta de grado , la puerta puede etiquetarse mediante 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 0 se llaman entradas u hojas . Las puertas de grado 0 se denominan salidas . Si hay un borde de puerta a puerta en el gráfico, entonces se le llama hijo de . Suponemos que hay un orden en los vértices del gráfico, por lo que podemos hablar del ésimo hijo de una puerta cuando es menor que el grado exterior 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 puerta es la longitud del camino más largo desde el principio hasta una puerta de salida. En particular, las puertas de grado 0 son las únicas puertas de profundidad 1. La profundidad de un circuito es la profundidad máxima de cualquier puerta. ${\displaystyle g}$ ${\displaystyle G}$ ${\displaystyle g}$

Nivel ${\displaystyle i}$ es el conjunto de todas las puertas de profundidad . Un circuito nivelado es un circuito en el que los bordes de las puertas de profundidad provienen únicamente de las puertas de profundidad o de las entradas. En otras palabras, los bordes sólo 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 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 se puede ver como una función de a . Es entonces habitual considerar una familia de circuitos , una secuencia de circuitos indexados por los números enteros donde el circuito tiene variables. Por tanto, las familias de circuitos pueden verse 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 ancho pueden extenderse naturalmente a familias de funciones, convirtiéndose en funciones de a ; por ejemplo, es el tamaño del décimo circuito 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 solucionable .

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

Ver también

• Complejidad del circuito aritmético
• 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 los circuitos . Berlín: Springer. ISBN 978-3-540-64310-4.
• Yang, Ke (2001). "La evaluación del circuito de números enteros está completa en PSPACE". Revista de Ciencias de la Computación y de Sistemas . 63 (2, septiembre de 2001): 288–303. doi : 10.1006/jcss.2001.1768 . ISSN  0022-0000.