NC (complessità)

Nella teoria della complessità i problemi NC sono i problemi efficientemente parallelizzabili, ovvero risolvibili in tempo polilogaritmico, avendo a disposizione una quantità di hardware polinomiale rispetto alla dimensione dell'input.

La classe NC prende il nome dallo studioso Nick Pippengers, suo primo ideatore.

Logica e circuiti

Per poter definire la NC è necessario introdurre un opportuno criterio di misura del costo di una computazione o equivalentemente di un algoritmo o problema. Come è noto ogni problema di decisione può essere opportunamente codificato in un problema definito sull'alfabeto A = {0,1}. Con tale ipotesi una generica macchina di Turing opera su input e restituisce in output stringhe di bit in A = {0,1}. Il particolare problema di decidere un linguaggio si riduce quindi a:

Dato w appartenente a {0,1}* se w appartiene ad un sottoinsieme S di {0,1}ⁿ la computazione restituisce 1 altrimenti 0.

Possiamo quindi associare ad ogni stringa

w\in S\subseteq \{0,1\}^{*}

un valore in A = {0,1} a seconda dell'esito della computazione della macchina di Turing su w. In altre parole possiamo definire delle funzioni che, con input w, restituiscono un valore 0 o 1 e che identificano un dato linguaggio. Ognuna di queste funzioni può essere rappresentata graficamente da un circuito booleano riconoscitore. Infatti tali funzioni possono essere espresse come composizione di tre particolari funzioni di base che sono: NOT, AND e OR le quali sono gli elementi costituenti di un circuito.

Circuito booleano riconoscitore

Un circuito booleano riconoscitore è un grafo diretto aciclico costituito da n + q nodi g₁,...,g_{n + q} i cui archi esprimono le relazioni funzionali tra i valori di input del circuito e l'output. I primi n nodi sono di input, hanno solo una linea di output e forniscono su di essa i bit di una stringa x = b₁,...,b_n. Gli altri q nodi sono nodi di circuito (porte logiche) corrispondenti a operatori booleani AND, OR, NOT ed hanno, rispettivamente, 2, 2, 1 linee di input e una linea di output. La linea di output della porta g_{n + q} (nodo di output) fornisce il risultato del calcolo effettuato dal circuito.

Per misurare la complessità del circuito possiamo utilizzare varie metriche. Le più comuni sono

DIM(c): Il numero di porte che costituisce il circuito.
PROF(c): La massima lunghezza di un cammino dal nodo di input ad un nodo di output.

Valore calcolato da circuito

Un interessante problema è quello di decidere il valore calcolato da un circuito. Tale problema può essere espresso nel seguente modo:

Dato un circuito Booleano c_n con n nodi di input ed una stringa w appartenente a {0,1}ⁿ decidere se f_c(w) = 1 dove f_c(w) è il valore fornito in output dal circuito.

Si noti che risolvere tale problema di decisione è equivalente a calcolare la funzione booleana f:{0,1}ⁿ → {0,1} su input w cioè f(b₀,...,b_n-1). Tale valore è calcolato attraverso un circuito c_n con una sequenza di valori in input w = b₀,...,b_n-1. f_c(w) = 1 se e solo se f(b₀,...,b_n-1) = 1.

In definitiva risolvere il problema di decisione del valore calcolato da un circuito è equivalente a calcolare una funzione attraverso un circuito booleano riconoscitore. Un importante risultato teorico è quello che dimostra la P-completezza di tale problema rispetto a Karp-riduzioni operanti in spazio logaritmo.

Dimostrazione

Si consideri una macchina di Turing deterministica <Σ, b_-, Q, q₀, F, δ>, e si suppongano vere le seguenti ipotesi:

la macchina opera in tempo O(p(|x|)) e spazio O(p(x));
la macchina ha nastro seminfinito;
la macchina cicla se raggiunge una configurazione finale.

La computazione di tale macchina può essere descritta in forma matriciale dove ogni riga della matrice rappresenta una configurazione della macchina durante la computazione. Per le ipotesi fatte la macchina opera in tempo al più p(x) quindi la matrice avrà al più p(x) + 1 righe (la prima riga contiene l'input). La generica riga, e quindi la generica configurazione, è descritta come

<a_{i0},|>,<a_{i1},|>,...,<a_{ih},q_{k}>,...,<a_{ip(x)|},|>.

Per l'ipotesi sullo spazio impiegato da M, la riga conterrà p(x) + 1 coppie T(i,j) = <a_i, q>. La matrice che descrive la computazione quindi avrà dimensione (p(x) + 1) × (p(x) + 1). Tutti gli elementi della matrice <a,q> possono essere codificati come una opportuna sequenza binaria di lunghezza k che dipende dal numero di caratteri dell'alfabeto e dal numero degli stati ma non dipende da n. Gli elementi della matrice sono vettori di {0,1}^k.

Con questa assunzione possiamo costruire un circuito che a partire dagli elementi della matrice opportunamente codificati restituisce 1 solo se M accetta la stringa di input. L'elemento T[i,j] della matrice dipende esclusivamente da T[i - 1, j - 1], T[i - 1, j], T[i - 1, j + 1], ciascuna funzione applicata a questi tre elementi restituisce complessivamente bit che contribuiscono alla codifica della cella T[i,j]. Il circuito è composto dalle normali porte logiche e da alcune porte addizionali che calcolano le seguenti funzioni:

S(i,j,k)={\begin{cases}1&{\mbox{se }}k<|Q|{\mbox{ e lo stato di }}T[i,j]=q\vee \ k=sQs{\mbox{ e lo stato di }}T[i,j]=s\\0&{\mbox{altrimenti}}\end{cases}}

T(i,j,k)={\begin{cases}1&{\mbox{se }}k<|\Sigma |{\mbox{ e il carattere di }}T[i,j]=a_{k}\ \vee \ k=|\Sigma |{\mbox{ e il carattere di }}T[i,j]=b_{-}\\0&{\mbox{altrimenti}}\end{cases}}

In pratica queste funzioni riconoscono se in un elemento della configurazione (la cella T[i,j]) contiene il carattere a_k e lo stato q_k. Con la precedente codifica tali funzioni possono essere viste come funzioni definite sul dominio {0,1}^k → {0,1}^k.

Con le precedenti assunzioni possiamo costruire il circuito nel seguente modo:

Input

La prima riga è costituita da n nodi di input che corrispondono alla rappresentazione binaria della stringa di input. La seconda riga è costituita da p(n) + 1 blocchi di calcolo B_{0,j} che rappresentano la codifica della configurazione iniziale del nastro dando in uscita i risultati delle funzioni C per ogni possibile carattere a ed S per ogni possibile stato. Sostanzialmente questa sezione è il risultato binario della applicazione delle funzioni S e C alla configurazione iniziale. Può essere vista come una parte "cablata" che poi unita alla codifica dell'input va in ingresso alla successiva sezione del circuito che è quella di calcolo. La sezione di input ha profondità 1 e dimensione p(n) + 1.

Calcolo

La sezione di calcolo è organizzata come una matrice di p(n) righe. Ciascuna riga è una opportuna combinazione delle output.

Famiglia di circuiti

Una famiglia C_n di circuiti è una sequenza di circuiti booleani calcolatori C_n = c₁,..., c_n che risolve un linguaggio L contenuto in {0,1}ⁿ, cioè che per ogni n>0

$f_{n}(x)={\begin{cases}1&{\mbox{se }}|x|=n\ \wedge \ x\in L\\0&{\mbox{altrimenti}}\end{cases}}$

Si noti che, mentre una stessa macchina di Turing è in grado di decidere ogni istanza di un problema di decisione, i diversi circuiti di una famiglia che decidono istanze di diversa lunghezza di uno stesso linguaggio non sono a priori correlati tra di loro. Ciò si esprime dal fatto che le macchine di Turing decidono insiemi di linguaggi ricorsivi mentre questo non è vero per le famiglie di circuiti. Per tale motivo i circuiti vengono definiti un modello di calcolo non uniforme. È possibile infatti creare esempi di linguaggi che non essendo ricorsivi non possono essere riconosciuti da macchine di Turing ma lo sono sa da una C_n.

Una famiglia di circuiti C = c₁, c₂,...,c_n si dice logspace uniforme se esiste una macchina di Turing che, operando in uno spazio di lavoro logaritmico e input n, genera una descrizione del circuito c_n.

Definizione formale di NC

La classe NC^k è la classe dei linguaggi le cui stringhe di lunghezza n vengono riconosciute da circuiti c_n logspace uniformi aventi profondità O(log(n)^k) e dimensione polinomiale.

Al variare di k quindi esistono differenti classi NC^k. La NC è l'unione infinita di tali classi cioè:

\mathrm {NC} =\cup _{k>0}\mathrm {NC} ^{k}.

Esempio

Un esempio di problema NC¹ è il controllo di parità su una stringa di bit.^[1] Il problema consiste nel contare il numero di 1 in una stringa costituita da 1 e 0. Una soluzione semplice consiste nel sommare tutti i bit della stringa. Dato che l'addizione è un'operazione associativa, $x_{1}+\cdots +x_{n}=(x_{1}+\cdots +x_{n/2})+(x_{n/2}+1+\cdots +x_{n})$ . Applicando ricorsivamente questà proprietà, è possibile costruire un albero binario di lunghezza $O(log(n))$ in cui ogni singola somma tra due bit $x_{i}$ e $x_{j}$ è esprimibile mediante operatori logici basilari, per esempio tramite l'espressione booleana $(x_{i}\land \neg x_{j})\lor (\neg x_{i}\land x_{j})$ .

Relazione tra NC e le altre classi

NC ⊆ P

Consideriamo una stringa x di taglia |x| = n; per determinare se x appartiene ad L generiamo innanzitutto il circuito c_n, di dimensione L(n), operando in spazio O(log L(n)). Poiché L(n) è polinomiale, lo spazio di lavoro della macchina di Turing è O(log L(n)) = O(log n) e quindi il tempo di costruzione del circuito è polinomiale. Successivamente, ancora in tempo polinomiale, possiamo simulare il comportamento del circuito c_n e decidere se x appartiene a L.

NC^k ⊆ DSPACE(log(n)^k)

Vale il seguente risultato di cui non viene fornita la dimostrazione. Dato un circuito c_n logspace uniforme avente DIM(c) e PROF(C) esiste una macchina di Turing che calcola il valore del circuito usando spazio al più O(PROF(C) + log(DIM(c)).

Da ciò osserviamo che essendo PROF(C) è O(log(n))^k per quanto visto in precedenza e combinando con il suddetto risultato otteniamo che: lo spazio di lavoro della macchina di Turing è O(log(n))^k + O(log(n)) = O(log(n))^k

La principale implicazione di questo risultato è che NC¹ è contenuto in LOGSPACE.

NLOGSPACE ⊆ NC²

Vale il seguente risultato di cui non viene fornita la dimostrazione. Se L appartiene a PSPACE(s(n) con s(n) ≥ log(n) allora L è riconosciuto da una famiglia uniforme di circuiti booleani avente profondità O(s(n)²).

Consideriamo un linguaggio L appartenente a NLOGSPACE, abbiamo che NLOGSPACE è contenuto in PSPACE(log(n)), quindi per il precedente risultato esiste una famiglia di circuiti C_n logspace uniforme che riconosce il linguaggio L avente profondità O(log(n)²) quindi L appartiene a NC².

Da questo risultato segue che

\mathrm {NC} ^{1}\subseteq \mathrm {LOGSPACE} \subseteq \mathrm {NLOGSPACE} \subseteq \mathrm {NC} ^{2}

NC è uguale a P?

Com'è possibile dimostrare, NC è un sottoinsieme di P, quindi diventa importante capire quali sono i problemi in P, che sono anche in NC, per i quali è possibile trovare algoritmi paralleli e ancora più importante è capire se NC = P. Allo stato attuale delle conoscenze tale relazione non è stata dimostrata, ma si pensa che le due classi siano distinte, cioè che esistano problemi in P che possono essere risolti esclusivamente in maniera sequenziale. In particolare si pensa che ciò accada per i problemi che risultano completi in P in base a riduzioni LOGSPACE.

Note

^ (EN) David Mix Barrington e Alexis Maciel, Lecture 2: The Complexity of Some Problems (PDF), in IAS/PCMI Summer Session 2000 - Clay Mathematics Undergraduate Program - Basic Course on Computational Complexity, Clarkson University, 18 luglio 2000. URL consultato l'11 novembre 2021.

Voci correlate

Portale Informatica

Portale Matematica

[1] (EN) David Mix Barrington e Alexis Maciel, Lecture 2: The Complexity of Some Problems (PDF), in IAS/PCMI Summer Session 2000 - Clay Mathematics Undergraduate Program - Basic Course on Computational Complexity, Clarkson University, 18 luglio 2000. URL consultato l'11 novembre 2021.

[1]