NC (complessità)

Da Wikipedia, l'enciclopedia libera.

Indice 1 Introduzione 2 Logica e Ciurcuiti 2.1 Circuito Booleano riconoscitore 2.2 Valore calcolato da circuito 2.3 Famiglia di circuiti 3 Definizione formale di NC 4 Relazione tra NC e le altre classi 4.1 4.2 4.3 5 Esempi di problemi in NC

[modifica] Introduzione

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. Com'è possibile dimostrare 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.

La classe NC prende il nome dallo studioso Nick Pippengers che le ha introdotte per primo

[modifica] Logica e Ciurcuiti

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 MdT 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 se la computazione restituisce 1 altrimenti 0.

Possiamo quindi associare ad ogni stringa un valore in A={0,1} a seconda dell'esito della computazione della MdT su w. In altre parole possiamo definire delle funzioni che con input w restituiscono un valore 0 o 1 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.

[modifica] 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) corrisponedenti 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

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

[modifica] Valore calcolato da circuito

Un interessante problema di decisione e il problema valora calcolato da circuito. Tale problema può essere espresso nel seguente modo:

Dato un circuito Booleano c_n con n nodi di input ed una stringa 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 su input w cioè f(b₀,...,b_{n − 1}). Tale valore è calcolato attraverso un circuito c_n con una sequenza di input w = b₀,...,b_{n − 1} di valori in input. f_c(w) = 1 se e solo se f(b₀,...,b_n − 1) = 1.

In definitiva risolvere il problema di decisione valore calcolato di 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 Touring 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à al p(x)+1 coppie T(i,j) = < a_i,q > . La matrice che descrive la computazione quindi avrà dimensione (p(x)+1) x (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 contribuisce alla codifica della cella T[i,j]. Il circuito è composto dalle normali porte logiche e da alcune porte addizionali che calcolano le seguenti funzioni:

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 .

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

[modifica] Famiglia di circuiti

Una famiglia C_n di circuiti è una sequenza di circuiti Booleni calcolatori C_n = c₁,...,c_n che risolve un linguaggio cioè che per ogni n>0

fn(x) = 1 se |x| = n ed x ∈ L, 0 altrimenti

Si noti che, mentre una stessa MT è 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. Cio si esprime dal fatto che le MdT decidono insiemi di linugaggi ricorsvi menter questo non è vero per le famiglie di circuiti.Per tale motivo i circuiti vengono definiti un modello di calcolo non uniforme. È possibile creare esempi di linugaggi infatti che non essendo ricorsivi non possono essere riconosciuti da MdT ma lo sono sa da una C_n

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

[modifica] Definizione formale di NC

La classe NC^k è la classe dei linguaggi le cui stringhe di lunghezza n vengono riconosciute da ciurcuiti 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è:

[modifica] Relazione tra NC e le altre classi

[modifica]

Consideriamo una stringa x di taglia , per determinare se 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 MdT è O(logL(n)) = O(logn) 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 .

[modifica]

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 MDT che calcolca 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 MdT è O(log(n))^k + O(log(n)) = O(log(n))^k

La principale implicazionde di questo risultato è che

[modifica]

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

Consideriamo un linguaggio , abbiamo che , quindi per il precedente risultato esiste una famgilia di circuiti C_n logspace uniforme che riconosce il linguaggio L avente profondità O(log(n)²) quindi .

Da questo risultato segue che

[modifica] Esempi di problemi in NC

1.2 Il linguaggio parità Sia parità = {x 2 {0, 1}� | x ha un numero dispari di 1} ovvero sia parità il linguaggio costituito dalle stringhe binarie aventi un numero dispari di 1. Ad esempio 1011 2 parità mentre " /2 parità. Il linguaggio parità è un linguaggio molto semplice (infatti è anche un linguaggio regolare) e può essere deciso da un circuito nc1. Per vedere come, si consideri una stringa “composta” xy. Questa stringa ha un numero dispari di 1 se e solo se x ne ha un numero pari e y un numero dispari o viceversa. Quindi, indicando con p(x) la funzione caratteristica dell’insieme parità, abbiamo p(xy) = p(x) � p(y) dove � indica la somma modulo due, o equivalentemente, l’operatore logico di OR esclusivo (XOR). Applicando ripetutamente questa proprietà ad una stringa di n bit x = x1 . . . xn, troviamo p(x) = p(x1) � . . . � p(xn). Questa somma può essere calcolata velocemente in parallelo con un albero binario di XOR di profondità O(log n). L’operatore logico XOR non è disponibile direttamente nel nostro modello di circuiti ma possiamo realizzarlo facilmente notando che x � y = (¬x ^ y) _ (x ^ ¬y). Abbiamo così dimostrato che parità 2 nc1 e che quindi la parità di una stringa può essere calcolata in tempo parallelo O(log n). Esercizio 1.1. Dimostrare che parità /2 nc0. Quali linguaggi appartengono alla classe nc0? Esercizio 1.2. Scrivere una espressione regolare che descriva il linguaggio parità. 1 PROBLEMI IN NC 2 1.3 Moltiplicazione di matrici booleane Siano A e B due matrici n × n a elementi zero e uno. Vogliamo costruire un circuito nc1 che calcoli il prodotto C = AB. Partendo dalla definizione di prodotto tra matrici abbiamo: Cij = Xn k=1 AikBkj che nel contesto booleano si può riscrivere come Cij = _n k=1 Aik ^ Bkj . Questa formula fornisce già un possibile circuito, ma l’idea non basta perch´e l’OR della formula ha un numero arbitrariamente alto (n) di ingressi mentre nel nostro modello le porte logiche possono avere al più due ingressi. Analogamente a quanto fatto nel caso precedente, comunque, possiamo calcolare questo OR a n ingressi con un albero binario di OR a due ingressi, di profondità O(log n). Abbiamo quindi che per calcolare Cij (un elemento della matrice prodotto) sono sufficienti n porte AND e circa n porte OR per un totale di O(n) porte e un tempo parallelo pari a O(log n) (profondità dell’albero). In questo modo tutti gli n2 elementi della matrice C possono essere calcolati in parallelo nello stesso tempo utilizzando O(n3) porte logiche. Quindi anche la moltiplicazione di matrici booleane è un problema risolvibile con circuiti nc1. Nota. Il nostro modello di calcolo parallelo può essere collegato con un modello più pratico di macchine a memoria condivisa (PRAM). Si può dimostrare che un problema che richiede un circuito di profondità f(n) e dimensione g(n) può essere risolto nel modello PRAM in tempo O(f(n)) con O(g(n)/f(n)) processori. Nel caso della moltiplicazione di matrici, ad esempio, avremmo un tempo parallelo O(log n) con O(n3/ log n) processori. Se i processori disponibili sono meno di g(n)/f(n), ad esempio p(n), si può ribilanciare il loro carico di lavoro per ottenere un tempo parallelo di O(f(n)+g(n)/p(n)). Questo principio va sotto il nome di principio di Brent. È da notare, comunque, che nel nostro modello non si considerano i costi della comunicazione tra i vari processori. 1.4 Raggiungibilità Il problema della raggiungibilità è il seguente: dato un grafo orientato G, è possibile raggiungere il nodo n a partire dal nodo 1? L’algoritmo classico per risolvere questo problema visita il grafo a partire dal nodo 1 finch´e non si incontra il nodo n o finch´e non ci sono più nuovi nodi da visitare. Questo algoritmo però non può essere parallelizzato in modo efficiente, dato che un cammino dal nodo 1 al nodo n potrebbe arrivare ad avere una lunghezza pari a n−1, quando invece vogliamo determinare se questo cammino esiste in tempo O(logk n) per qualche k. Usiamo quindi un approccio totalmente diverso. Assumiamo di avere in ingresso la matrice di adiacenza A del grafo G0 ottenuto da G aggiungendo 1 PROBLEMI IN NC 3 tutti i loop da un nodo a se stesso. Quindi Aij = 1 se e solo se esiste un arco da i a j in G oppure i = j. Consideriamo ora l’elemento (i, j) della matrice A2: A2 ij = _n k=1 Aik ^ Akj . Come abbiamo visto precedentemente, possiamo calcolare questa matrice con un circuito nc1. Non è difficile rendersi conto dalla definizione che A2 ij è pari a 1 se e solo se esiste un cammino di lunghezza al più due dal nodo i al nodo j. Analogamente Al ij vale 1 se e solo se esiste un cammino di lunghezza al più l dal nodo i al nodo j. Ipotizziamo ora per un momento che n sia una potenza di due. Possiamo ottenere la matrice R = An elevando ripetutamente al quadrato la matrice A: R = An = (((A2)2) . . .)2 (log n volte). Dato che ogni cammino in G ha lunghezza minore di n, l’elemento (i, j) di questa matrice vale 1 se e solo se esiste un cammino da i a j in G. Quindi dal nodo 1 si può raggiungere il nodo n se e solo se R1n = 1. Abbiamo così che il circuito che calcola la matrice R può essere ottenuto collegando in cascata log n circuiti che calcolano il quadrato di una matrice. Dato che ognuno di questi circuiti ha una profondità pari a O(log n) e dimensione O(n3), otteniamo un circuito con una profondità totale O(log2 n) e una dimensione totale O(n3 log n). raggiungibilità è quindi in nc2. Esercizio 1.3. Adattare l’algoritmo al caso in cui n non sia necessariamente una potenza di due. 1.5 Addizione Siano a = an−1 . . . a0 e b = bn−1 . . . b0 due interi nella loro rappresentazione a n bit. Vogliamo calcolare la loro somma s, di n + 1 bit. Una possibile soluzione è rappresentata da una cascata di addizionatori di bit con riporto (full-adder); ogni addizionatore riceve in ingresso ai, bi e ci (il riporto generato dall’addizionatore precedente) e fornisce in uscita si e ci+1: si = ai � bi � ci ci+1 = (ai ^ bi) _ (ai ^ ci) _ (bi ^ ci). Questa soluzione è però inerentemente sequenziale dato che porta ad un circuito di profondità �(n). Usiamo quindi un approccio diverso detto previsione del riporto. Diciamo che la posizione i genera un riporto se sia ai che bi sono pari ad 1. Diciamo invece che la posizione i propaga il riporto se almeno uno tra ai e bi è pari ad 1. Avremo un riporto entrante nella posizione i+1 se e solo se: (1) la posizione i genera un riporto oppure (2) la posizione i − 1 genera un riporto e la posizione i lo propaga, oppure (3) la posizione i − 2 genera un riporto e 1 PROBLEMI IN NC 4 le posizione i − 1 ed i lo propagano, oppure ecc. In simboli, sia gi = ai ^ bi, pi = ai _ bi. Allora per ogni i tra 1 ed n abbiamo: ci = i_−1 j=0 gj ^ pj+1 ^ pj+2 ^ . . . ^ pi−1. Dato che una volta noti i bit ci, i bit si possono essere calcolati facilmente, questa formula fornisce un circuito di profondità costante che calcola la somma di due interi. Questo circuito però non è un circuito della classe nc dato che sfrutta porte logiche AND e OR con fan-in maggiore di due. Per renderlo tale, trasformiamo come nel caso della moltiplicazione di matrici booleane ogni porta a m ingressi in un albero binario di porte a due ingressi di profondità O(logm). La profondità di questo nuovo circuito è ora al più O(log n) e, dato che la dimensione del circuito è ancora polinomiale, abbiamo dimostrato che l’addizione di interi può essere calcolata con circuiti nc1. Esercizio 1.4. La classe ack è definita come l’insieme dei linguaggi decidibili da famiglie (logspace-uniformi) di circuiti di dimensione polinomiale e profondità O(logk n), che fanno uso, oltre che di porte NOT, di porte AND e OR con numero di ingressi illimitato. Dimostrare che nck � ack � nck+1 per ogni k � 0. Esercizio 1.5. Dimostrare che nc1 coincide con la classe di linguaggi decidibili da famiglie (logspace-uniformi) di circuiti di profondità O(log n) e fan-in 2. Il risultato è generalizzabile a nck? 1.6 Moltiplicazione Per costruire un circuito per la moltiplicazione, usiamo la stessa strategia di tipo divide et impera che abbiamo usato per il linguaggio parità. Calcoliamo gli n numeri b · ai · 2i per i che va da 0 a n − 1; ognuno di questi numeri può essere calcolato con un circuito di profondità costante. Dopodich´e, addizioniamo questi numeri di 2n bit a due a due usando un albero binario di addizioni. Dato che ognuna di queste addizioni può essere calcolata da un circuito nc1, otteniamo un circuito nc2 per la moltiplicazione. Questo risultato può essere migliorato per ottenere un circuito di profondità O(log n), usando un accorgimento che potremmo chiamare “tre al prezzo di due”: se x, y e z sono tre numeri a 2n bit, possiamo addizionare i loro bit i-esimi ed ottenere un numero a due bit: xi +yi +zi = 2 · ui +vi. Ora i bit ui e vi formano due altri numeri u e v, con la proprietà che x+y+z = 2u+v. Abbiamo così ridotto il problema di sommare tre interi a quello di sommarne due: v, e u con uno zero aggiunto alla fine. Quindi per sommare n interi a 2n bit li suddividiamo in triple e in uno stadio parallelo rimpiazziamo ognuna di queste triple con due interi di 2n + 1 bit. Questo vuol dire che ad ogni stadio il numero di interi viene moltiplicato per 2 3 . Dopo al più log 3 2 2n stadi saremo rimasti con uno o due interi, che sommiamo per ottenere il risultato finale. Quindi anche la moltiplicazione può essere calcolata da una famiglia di circuiti nc1. 1 PROBLEMI IN NC 5 1.7 Ordinamento Il problema dell’ordinamento di n numeri interi può essere ridotto al problema dell’ordinamento di n bit. A sua volta questo problema può essere risolto attraverso l’uso di comparatori (un comparatore è un circuito a due ingressi la cui prima uscita è il bit minore e la cui seconda uscita è il bit maggiore). Naturalmente per ottenere un ordinamento veloce dal punto di vista parallelo, vogliamo utilizzare un circuito di comparatori di piccola profondità. Omettiamo qui i dettagli, ma si può dimostrare che l’ordinamento di n bit può essere realizzato attraverso una rete di comparatori di profondità O(log2 n). Si veda, ad esempio, il libro Introduzione agli algoritmi di Cormen, Leiserson e Rivest. Dato che la famiglia di circuiti risultante ha anche dimensione polinomiale in n ed è logspace-uniforme, l’ordinamento è in nc2. Esercizio 1.6. Realizzare un comparatore di bit attraverso delle porte logiche. Usare più comparatori per progettare un circuito a quattro ingressi e quattro uscite che ordini i suoi ingressi, cercando di ottenere la minima profondità

possibile.