Complessità dei circuiti

In informatica teorica, la complessità dei circuiti è un ramo della teoria della complessità computazionale nel quale le funzioni booleane sono classificate secondo la dimensione o la profondità dei circuiti booleani che le computano. Si parla quindi della complessità di un circuito booleano. Una nozione collegata è la complessità dei circuiti di un linguaggio ricorsivo che è deciso da una famiglia di circuiti (vedi sotto). Un circuito booleano con bit di input è un grafo aciclico diretto nel quale ogni nodo (solitamente chiamato porta in questo contesto) è o un nodo di input di 0 etichettato da uno degli bit dell'input, una porta AND, una porta OR o una porta NOT. Una di queste porte è designata come la porta dell'output. Tale circuito computa naturalmente una funzione dei suoi input. La dimensione di un circuito è il numero di porte che contiene e la sua profondità è la lunghezza massima di un cammino da una porta di input alla porta di output. Ci sono due nozioni principali di complessità dei circuiti (queste sono delineate in Sipser (1997):324). La complessità della dimensione dei circuiti di una funzione booleana è la dimensione minimale di qualsiasi circuito che computi . La complessità della profondità dei circuiti di una funzione booleana è la profondità minimale di qualsiasi circuito che computi . Queste nozioni si generalizzano quando si consideri la complessità dei circuiti di un linguaggio ricorsivo: un linguaggio formale può contenere stringhe con molte lunghezze diverse di bit. I circuiti booleani, tuttavia, comsentono soltanto un numero fisso di bit degli input. Perciò nessun circuito booleano singolo è capace di decidere tale linguaggio. Per tenere conto di tale possibilità, si considerano famiglie di circuiti dove ciascun accetta input di dimensione . Ciascuna famiglia di circuiti genererà naturalmente un linguaggio ricorsivo producendo quando una stringa è una componente della famiglia, e altrimenti. Diciamo che una famiglia di circuiti è di dimensione minimale se non c'è nessun'altra famiglia che decide su input di qualsiasi dimensione, , con un circuito di dimensione minore di (rispettivamente per le famiglie di profondità minimale). Quindi, la complessità della dimensione dei circuiti di un linguaggio ricorsivo è definita come la funzione , che collega una lunghezza di bit di un input, , alla complessità della dimensione dei circuiti del circuito minimale che decide se gli input di quella lunghezza sono in . La complessità della profondità dei circuiti è definita in modo simile. Le classi di complessità definite in termini di circuiti booleani includono AC0, AC, ed NC.