Complexidade de circuitos

No ramo da Ciência da computação teórica, complexidade de circuitos é um ramo da Teoria da complexidade computacional onde Função booleanas são classificadas de acordo com o tamanho ou o grau dos Circuitos booleanos que as computam. Ele trata da complexidade de um circuito Booleano. Uma noção é a complexidade do circuito de uma linguagem recursiva que é decidida por uma família de circuitos (veja mais a seguir). Um circuito booleano com bits de entrada é um grafo acíclico dirigido onde cada nó (normalmente chamados de porta neste contexto) é um desses quatro elementos: um nó de entrada cujo grau de entrada é 0 representado por um dos bits de entrada, uma porta AND, uma porta OR ou uma porta NOT. Uma dessas portas é designada porta de saída. Tal circuito naturalmente computa uma função a partir de suas entradas. O tamanho de um circuito é o numero de portas que ele contém seu grau é definido pelo comprimento do maior caminho de uma porta de entrada até uma porta de saída. Existem dois conceitos principais da complexidade de circuitos (esses dois conceitos são definidos no Sipser (1997)). A complexidade do tamanho do circuito de uma função Booleana é o tamanho mínimo de qualquer circuito que compute . A complexidade do grau do circuito de uma função Booleana é o grau mínimo de qualquer circuito que compute . Essas noções também se aplicam quando se considera a complexidade do circuito de uma linguagem recursiva: Uma linguagem formal pode conter muitas palavras com uma quantidade diversa de bits por palavra. Circuitos booleanos, no entanto, só permitem um número fixo de bits por entrada. Logo, nenhum circuito booleano é capaz de decidir sozinho uma linguagem recursiva. Para permitir que isso seja feito, deve-se considerar famílias de circuitos onde cada aceita entradas de tamanho . Cada família de circuito vai naturalmente gerar uma linguagem recursiva ao dar como saída quando uma palavra for membro da família, e caso contrário. Dizemos que uma família de circuitos tem tamanho mínimo se não existe outra família que decida com um circuito menor do que o tamanho de , para entradas de tamanho . O mesmo se aplica para famílias de grau mínimo. Sendo assim, a complexidade do tamanho do circuito de uma linguagem recursiva é definia como a função , que relaciona o tamanho dos bits de uma entrada, , com a complexidade do tamanho de um circuito mínimo que decide se entradas desse tamanho estão em . A complexidade do grau do circuito é definida similarmente. Classe de complexidades definida em termos de circuitos booleanos incluem , , e .