NC (complessità)

Da Wikipedia, l'enciclopedia libera.
Se riscontri problemi nella visualizzazione dei caratteri, clicca qui.

Nella teoria della complessità i problemi NC sono i problemi efficientemente parallelizzabili cioè che possono essere risolti 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 che le ha introdotte per primo.

Logica e circuiti[modifica | modifica sorgente]

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 ad A = {0,1}* se w appartiene ad un sottoinsieme S di {0,1}n 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[modifica | modifica sorgente]

Un circuito booleano riconoscitore è un grafo diretto aciclico costituito da n + q nodi g1,...,gn + 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 = b1,...,bn. 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 gn + 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

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

Valore calcolato da circuito[modifica | modifica sorgente]

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

Dato un circuito Booleano cn con n nodi di input ed una stringa w appartenente a {0,1}n</math> decidere se fc(w) = 1 dove fc(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}n → {0,1} su input w cioè f(b0,...,bn-1). Tale valore è calcolato attraverso un circuito cn con una sequenza di valori in input w = b0,...,bn-1. fc(w) = 1 se e solo se f(b0,...,bn-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[modifica | modifica sorgente]

Si consideri una macchina di Turing deterministica <Σ, b-, Q, q0, 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) = <ai, 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 ak e lo stato qk. 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[modifica | modifica sorgente]

Una famiglia Cn di circuiti è una sequenza di circuiti Booleni calcolatori Cn = c1,..., cn che risolve un linguaggio L contenuto in {0,1}n, 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 Cn.

Una famiglia di circuiti C = c1, c2,...,cn 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 cn.

Definizione formale di NC[modifica | modifica sorgente]

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

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

\mathrm{NC} = \cup_{k>0} \mathrm{NC}^k.

Relazione tra NC e le altre classi[modifica | modifica sorgente]

NC ⊆ P[modifica | modifica sorgente]

Exquisite-kfind.png Per approfondire, vedi P (complessità).

Consideriamo una stringa x di taglia |x| = n; per determinare se x appartiene ad L generiamo innanzitutto il circuito cn, 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 cn e decidere se x appartiene a L.

NCk ⊆ DSPACE(log(n)k)[modifica | modifica sorgente]

Vale il seguente risultato di cui non viene fornita la dimostrazione. Dato un circuito cn 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 NC1 è contenuto in LOGSPACE.

NLOGSPACE ⊆ NC2[modifica | modifica sorgente]

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)2).

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 Cn logspace uniforme che riconosce il linguaggio L avente profondità O(log(n)2) quindi L appartiene a NC2.

Da questo risultato segue che

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

NC è uguale a P?[modifica | modifica sorgente]

Exquisite-kfind.png Per approfondire, vedi Classi di complessità P e NP.

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.

Bibliografia[modifica | modifica sorgente]

Voci correlate[modifica | modifica sorgente]