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 $C_{1},C_{2},\ldots$ (vedi sotto).

Un circuito booleano con $n$ bit di input è un grafo aciclico diretto nel quale ogni nodo (solitamente chiamato porta in questo contesto) è o un nodo di input di grado interno 0 etichettato da uno degli $n$ 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 $n$ 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 $f$ è la dimensione minimale di qualsiasi circuito che computi $f$. La complessità della profondità dei circuiti di una funzione booleana $f$ è la profondità minimale di qualsiasi circuito che computi $f$.

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 $C_{1},C_{2},\ldots$ dove ciascun $C_{n}$ accetta input di dimensione $n$. Ciascuna famiglia di circuiti genererà naturalmente un linguaggio ricorsivo producendo $1$ quando una stringa è una componente della famiglia, e $0$ altrimenti. Diciamo che una famiglia di circuiti è di dimensione minimale se non c'è nessun'altra famiglia che decide su input di qualsiasi dimensione, $n$, con un circuito di dimensione minore di $C_{n}$ (rispettivamente per le famiglie di profondità minimale).

Quindi, la complessità della dimensione dei circuiti di un linguaggio ricorsivo $A$ è definita come la funzione $t:\mathbb {N} \to \mathbb {N}$, che collega una lunghezza di bit di un input, $n$, alla complessità della dimensione dei circuiti del circuito minimale $C_{n}$ che decide se gli input di quella lunghezza sono in $A$. La complessità della profondità dei circuiti è definita in modo simile.

Le classi di complessità definite in termini di circuiti booleani includono AC⁰, AC, TC⁰ ed NC.

Uniformità

I circuiti booleani sono uno degli esempi primari dei cosiddetti modelli di computazione non uniformi, nel senso che input di lunghezze diverse sono processati da circuiti diversi, in contrasto con i modelli uniformi come le macchine di Turing dove lo stesso dispositivo computazionale è usato per tutte le possibili lunghezze degli input. Un singolo problema computazionale è perciò associato a una particolare famiglia di circuiti booleani $C_{1},C_{2},\dots$ dove ciascun $C_{n}$ è il circuito che gestisce gli input di n bit. Su queste famiglie è spesso imposta una condizione di uniformità, che richiede l'esistenza di una qualche macchina di Turing con limiti di risorse che, sull'input n, produce una descrizione del singolo circuito $C_{n}$. Quando questa macchina di Turing ha un tempo di esecuzione polinomiale in n, si dice che la famiglia è P-uniforme. Il requisito più rigoroso dell'uniformità in DLOGTIME è di particolare interesse nello studio delle classi di circuiti a bassa profondità come AC⁰ o TC⁰.

Uniforme in tempo polinomiale

Una famiglia di circuiti booleani $\{C_{n}:n\in \mathbb {N} \}$ è uniforme in tempo polinomiale se esiste una macchina di Turing deterministica M, tale che

• M funziona in tempo polinomiale
• Per tutte le $n\in \mathbb {N}$, M produce una descrizione di $C_{n}$ sull'input $1^{n}$.

Uniforme in spazio logaritmico

Una famiglia di circuiti booleani $\{C_{n}:n\in \mathbb {N} \}$ è uniforme in spazio logaritmico (o in logspace) se esiste una macchina di Turing deterministica M, tale che

• M funziona in tempo polinomiale
• Per tutte le $n\in \mathbb {N}$, M produce una descrizione di $C_{n}$ sull'input $1^{n}$.

Storia

La complessità dei circuiti risale a Shannon (1949), che dimostrò che quasi tutte le funzioni booleane su n variabili richiedono circuiti di dimensione Θ(2ⁿ/n). Malgrado questo fatto, i teorici della complessità non sono stati in grado di dimostrare i limiti inferiori dei circuiti superpolinomiali per specifiche funzioni booleane.

D'altro canto, i limiti inferiori superpolinomiali sono stati dimostrati sulla base di certe restrizioni imposte sulla famiglia di circuiti usati. La prima funzione per la quale furono mostrati i limiti inferiori dei circuiti superpolinomiali fu la funzione di parità, che computa la somma dei bit dei suoi input modulo 2. Il fatto che la parità non sia contenuta in AC⁰ fu stabilito per la prima volta indipendentemente da Ajtai (1983) e da Furst, Saxe e Sipser (1984). Successivi miglioramenti da parte di Håstad (1987) in realtà stabiliscono che qualsiasi circuito di profondità costante che computa la funzione di parità richiede la dimensione esponenziale. Smolensky (1987) dimostrò che questo è vero anche se il circuito è ampliato con porte che computano la somma dei bit dei suoi input modulo qualche numero primo p dispari.

Il problema della k-cricca è decidere se un dato grafo su n vertici ha una cricca di dimensione k. Per qualsiasi particolare scelta delle costanti n e k, il grafo può essere codificato in binario usando ${n \choose 2}$ bit che indicano per ciascun possibile spigolo se è presente. Allora il problema della k-cricca è formalizzato come una funzione $f_{k}:\{0,1\}^{n \choose 2}\to \{0,1\}$ tale che $f_{k}$ produce 1 se e solo se il grafo codificato dalla stringa contiene una cricca di dimensione k. Questa famiglia di funzioni è monotona e può essere computata da una famiglia di circuiti, ma si è mostrato che non può essere computata da una famiglia di dimensione polinomiale di circuiti monotoni (ossia, circuiti con porte AND e OR ma senza negazione). Il risultato originario di Razborov (1985) fu in seguito migliorato in un limite inferiore di dimensione esponenziale da Alon e Boppana (1987). Rossman (2008) mostra che i circuiti a profondità costante con porte AND, OR e NOT richiedono dimensione $\Omega (n^{k/4})$ per risolvere il problema della k-cricca anche nel caso medio. Tuttavia, c'è un circuito di dimensione $n^{k/4+O(1)}$ che computa $f_{k}$.

Raz e McKenzie in seguito dimostrarono che la gerarchia monotona NC è infinita (1999).

Il problema della divisione degli interi giace in TC⁰ uniforme (Hesse 2001).

Limiti inferiori dei circuiti

I limiti inferiori dei circuiti sono generalmente difficili. I risultati noti includono:

• La parità non è in AC⁰ non uniforme, provato da Ajtai (1983) e da Furst, Saxe e Sipser.
• TC⁰ uniforme non è contenuto in PP, provato da Allender.
• Le classi SP2, PP ed MA/1 (MA con po' di aiuto) non sono in SIZE(n^k) per qualsiasi costante k.
• Benché si sospetti che la classe in uniforme ACC⁰ non contenga la funzione di maggioranza, fu solo nel 2010 che Williams provò che ${\mathsf {NEXP}}\not \subseteq {\mathsf {ACC}}^{0}$.

È aperto se NEXPTIME ha circuiti TC⁰ non uniformi.

Le prove dei limiti inferiori dei circuiti sono fortemente connesse alla derandomizzazione. Una prova che P = BPP implicherebbe che o ${\mathsf {NEXP}}\not \subseteq {\mathsf {P/poly}}$ o quel permanente non possono essere computati da circuiti aritmetici non uniformi (polinomi) di dimensione e grado polinomiale.

Classi di complessità

Molte classi di complessità dei circuiti sono definite in termini di gerarchie di classe. Per ogni intero non negativo i, c'è una classe NCⁱ, che consiste di circuiti di dimensione polinomiale aventi profondità $O(\log ^{i}(n))$, che usano porte AND, OR e NOT con numero massimo di linee d'ingresso (fan-in) limitato. Possiamo parlare dell'unione NC di tutte queste classi. Considerando porte con numero massimo di linee d'ingresso non limitato, costruiamo le classi ACⁱ e AC. Costruiamo molte altre classi di complessità dei circuiti con le stesse restrizioni di dimensione e di profondità consentendo diversi insiemi di porte.

Relazione con la complessità temporale

diciamo che un certo linguaggio, $A$, appartiene alla classe di complessità temporale ${\text{TIME}}(t(n))$ per una qualche funzione $t:\mathbb {N} \to \mathbb {N}$. Allora $A$ ha complessità dei circuiti ${\mathcal {O}}(t^{2}(n))$

Bibliografia

• Miklós Ajtai, $\Sigma _{1}^{1}$-formulae on finite structures, in Annals of Pure and Applied Logic, vol. 24, 1983, 1–24.
• Noga Alon e Ravi B. Boppana, The monotone circuit complexity of Boolean functions, in Combinatorica, vol. 7, n. 1, 1987, 1–22.
• Merrick L. Furst, James B. Saxe e Michael Sipser, Parity, circuits, and the polynomial-time hierarchy, in Mathematical Systems Theory, vol. 17, n. 1, 1984, 13–27.
• Johan Håstad, Computational limitations of small depth circuits (PDF), Ph.D. thesis, Massachusetts Institute of Technology, 1987.
• William Hesse, Division is in uniform TC⁰, Proc. 28th International Colloquium on Automata, Languages and Programming, Springer, 2001, pp. 104–114.
• Ran Raz e Pierre McKenzie, Separation of the monotone NC hierarchy, in Combinatorica, vol. 19, n. 3, 1999, 403–435.
• Alexander A. Razborov, Lower bounds on the monotone complexity of some Boolean functions, in Mathematics of the USSR, Doklady, vol. 31, 1985, 354–357.
• Benjamin Rossman, On the constant-depth complexity of k-clique, STOC 2008: Proceedings of the 40th annual ACM symposium on Theory of computing, ACM, 2008, pp. 721–730, DOI:10.1145/1374376.1374480.
• Claude E. Shannon, The synthesis of two-terminal switching circuits, in Bell System Technical Journal, vol. 28, n. 1, 1949, pp. 59–98.
• Roman Smolensky, Algebraic methods in the theory of lower bounds for Boolean circuit complexity, Proc. 19th Annual ACM Symposium on Theory of Computing, ACM, 1987, pp. 77–82, DOI:10.1145/28395.28404.
• Vollmer Heribert, Introduction to Circuit Complexity: a Uniform Approach, Springer Verlag, 1999, ISBN 3-540-64310-9.
• Wegener Ingo, The Complexity of Boolean Functions, John Wiley and Sons Ltd, and B. G. Teubner, Stuttgart, 1987, ISBN 3-519-02107-2. Al tempo un influente libro di testo sull'argomento, noto comunemente come Blue Book (il "Libro azzurro"). Disponibile anche per lo scaricamento (PDF) su Electronic Colloquium on Computational Complexity.

Collegamenti esterni

• (EN) Appunti delle lezioni per un corso di Uri Zwick sulla complessità dei circuiti, su cs.tau.ac.il.
• (EN) http://ftp.cs.rutgers.edu/pub/allender/fsttcs.pdf, una panoramica sul campo del 1997 mediante le diapositive Archiviato il 3 marzo 2016 in Internet Archive. di Eric Allender