Complejidad del circuito
En informática teórica , la complejidad de los circuitos es una rama de la teoría de la complejidad computacional en la que las funciones booleanas se clasifican según el tamaño o la profundidad de los circuitos booleanos que las calculan. Una noción relacionada es la complejidad del circuito de un lenguaje recursivo que se decide mediante una familia uniforme de circuitos (ver más abajo).
Demostrar límites inferiores en el tamaño de los circuitos booleanos que calculan funciones booleanas explícitas es un enfoque popular para separar clases de complejidad. Por ejemplo, una clase de circuito prominente P / poli consta de funciones booleanas calculables por circuitos de tamaño polinomial. Demostrar que separaría P y NP (ver más abajo).
Un circuito booleano con bits de entrada es un gráfico acíclico dirigido en el que cada nodo (generalmente llamado puertas en este contexto) es un nodo de entrada de grado 0 etiquetado por uno de los bits de entrada, una puerta Y , una puerta O o una puerta NO . Una de estas puertas se designa como puerta de salida. Naturalmente, tal circuito calcula una función de sus entradas. El tamaño de un circuito es el número de puertas que contiene y su profundidad es la longitud máxima de una ruta desde una puerta de entrada a la puerta de salida.
Hay dos nociones principales de complejidad de circuito [1] La complejidad de tamaño de circuito de una función booleana es el tamaño mínimo de cualquier cálculo de circuito . La complejidad de la profundidad del circuito de una función booleana es la profundidad mínima de cualquier cálculo de circuito .
