Torna alla pagina di Informatica Teorica

 :: Informatica Teorica - Complessità nel tempo ::

Appunti & Dimostrazioni del 5 Maggio

Cenni teorici

Sia M una Macchina di Turing (da ora MdT) deterministica che si ferma su ogni ingresso. Il tempo di esecuzione o complessità nel tempo di M è la funzione f: N -> N, dove f(n) è il numero massimo di passi che M impiega su ogni ingresso di lunghezza n. Se f(n) è il tempo di esecuzione di M, diciamo che M è eseguita in tempo f(n) e che M è una tempo f(n) MdT.

Della complessità nel tempo non si dà una misura precisa, ma una stima risultante dall'analisi asintotica dell'algoritmo. In particolare introduciamo le notazioni O ("o grande") e o ("o piccolo").
Siano f e g due funzioni f,g: N -> R⁺. Diciamo che f(n) = O(g(n)) se esistono due interi positivi c e n₀ tali che per ogni intero n>=n₀: f(n) >= c*g(n)
Quando f(n) = O(g(n)) diciamo che g(n) è un limite superiore (upper bound) per f(n), o più precisamente che g(n) è un limite superiore asintotico per f(n), per enfatizzare il fatto che stiamo ignorando le costanti.
Se O può essere definita come una funzione asintoticamente "non maggiore" di un'altra (minore o uguale), con o piccolo definiamo una funzione asintoticamente "minore" di un'altra (strettamente minore). Facendo qualche esempio:

• n = o(nlog(logn))
• nlog(logn) = o(n(logn))
• n² = o(n³)

Perché abbiamo parlato di o grandi e o piccole? Perché quando si fa l'analisi asintotica di un algoritmo si considerano solo i termini di ordine maggiore che partecipano a formare il tempo di esecuzione complessivo, trascurando i coefficienti, le costanti e tutti i termini di grado inferiore.
Ad esempio: f(n) = 3n³ + 2n² + n + 100 = O(n³)

Concludiamo definendo cos'è una classe di complessità nel tempo:

Teorema 1 - sulle relazioni di complessità tra modelli

Dimostrazione

Consideriamo M una MdT con k nastri, ed S la corrispondente MdT a nastro singolo. S è costruita copiando i contenuti dei k nastri sul suo mettendoli in fila uno dopo l'altro e separandoli con un #. Perché S riesca a simulare un singolo passo di M su un certo nastro, dovrà prima posizionare la propria testina sul punto corrispondente, e solo dopo compiere l'operazione. Sappiamo dal testo del teorema che nel peggiore dei casi la testina di M impiegherà t(n) tempo per raggiungere il punto desiderato e compiere l'operazione, quindi avrà complessità O(t(n)). La complessità di S sarà dunque data dai contributi derivanti dalle seguenti operazioni:

• ricopiare correttamente il contenuto di M, impiegando O(n) passi
• simulare M su nastro singolo, impiegando t(n) passaggi ognuno con complessità O(t(n)). Ovvero: t(n)*O(t(n))=O(t²(n))

Dato che tra O(n) e O(t²(n)) il secondo è il contributo più importante, trascuriamo il primo è affermiamo che simulare una multinastro su MdT a nastro singolo richiede il quadrato del tempo di esecuzione della prima.

Teorema 2 - sulle relazioni di complessità tra modelli

Dimostrazione

Data una MdT non deterministica N con tempo di esecuzione t(n), sappiamo che è possibile creare una MdT deterministica D equivalente che intraprende ogni possibile ramo della computazione non deterministica. In particolare, dato un ingresso di lunghezza n (la grandezza della stringa w) ogni ramo dell'albero di computazione non deterministica di N avrà al massimo lunghezza t(n). Supponendo che ogni nodo possa avere al massimo b figli (ovvero le scelte legali della funzione di transizione), avremo al massimo b^t(n) foglie.
Per rendere più efficiente l'algoritmo, l'esplorazione dell'albero per cercare lo stato di accettazione non viene fatta in profondità (dalla radice alla foglia e poi da capo con un altro percorso), ma in ampiezza (controllando gli stati dei nodi livello per livello).
Il numero di nodi nell'albero è di poco inferiore al doppio delle foglie, quindi possiamo dare come limite superiore al numero di nodi O(b^t(n)). A questo punto, sapendo che il tempo di esplorazione dalla radice a qualunque nodo è pari a O(t(n)), e che nel caso peggiore bisognerà visitare tutti gli O(b^t(n)) nodi dell'albero, il tempo totale di esecuzione dell'algoritmo D è pari a:
O(t(n)*b^t(n)) = 2^O(t(n))

Facciamo qualche considerazione conclusiva sull'equivalenza O(t(n)*b^t(n))=2^O(t(n)):

• si tratta di un prodotto tra un polinomio e un'esponenziale, ed avendo quest'ultimo un ordine di grandezza maggiore, è possibile trascurare il primo e considerare come complessità dell'algoritmo solo O(b^t(n))
• per una serie di motivi che non ci interessano (che riguardano comunque la teoria della complessità), è possibile passare da O(b^t(n)) a O(2^t(n))
• siccome la base 2 è una costante, possiamo portare in alto l'o grande: O(2^t(n))=2^O(t(n))

Il teorema sembra già dimostrato, ma in realtà non va dimenticato che la D che simula N non è più una MdT a singolo nastro, ma per costruzione ne ha 3. Poco male: dal Teorema 1 sopra riportato sappiamo che ogni MdT multinastro t(n)-tempo ha una equivalente MdT a nastro singolo O(t²(n))-tempo. Quindi:
(2^O(t(n)))² = 2^O(2t(n)) = 2^O(t(n))

Dimostrazione conclusa.

Classe P

Introduciamo ora la classe P, ovvero la classe dei linguaggi che sono decidibili in tempo polinomiale su una MdT deterministica a singolo nastro. Si tratta di una classe matematicamente robusta, che non dipende quindi dal modello computazionale che sceglieremo per risolvere il problema.
I problemi in P, o tempo-polinomiali, sono una classe di problemi realisticamente risolvibili con un calcolatore. Per dimostrare che un problema è tempo-polinomiale bisognerà prima dare un limite polinomiale superiore (in notazione O grande) per il numero di passi che l'algoritmo usa per un ingresso di lunghezza n, poi esaminare ogni passo della descrizione dell'algoritmo per assicurarci che ogni passo sia tempo-polinomiale.

PATH è P?

Dato un grafo diretto G, il problema PATH ha come obiettivo quello di determinare se esiste un percorso diretto tra due nodi s e t. Più formalmente: PATH = {<G,s,t> | G è un grafo diretto che ha percorso diretto tra s e t}

Per dimostrare che PATH appartiene a P dovremo dimostrare che è risolvibile in tempo polinomiale. Una possibile strada è quella di partire da s e marcare tutti i nodi raggiungibili con passo 1, per poi ripetere l'operazione partendo da essi (raggiungendo una distanza da s pari a 2). L'operazione va ripetuta finché non è più possibile marcare nuovi nodi. A questo punto bisogna verificare se t è stato segnato o no: se sì PATH è vero, altrimenti no.
Costruiamo ora la MdT deterministica M che implementa l'algoritmo:

Facciamo l'analisi dell'algoritmo:

• i passi (1) e (4) sono ripetuti una sola volta
• i passi (2) e (3) (il loop) sono eseguiti m volte, dove m è il numero di nodi

Quindi, dato che il numero di passi è 1+1+m e che ognuno di essi ha complessità polinomiale, PATH è in P.

RELPRIME è P?

Prima di tutto, di cosa diavolo stiamo parlando? Il problema RELPRIME è quello che deve verificare se due numeri sono primi tra loro, ovvero se il più grande intero che li divide entrambi è 1. Più formalmente:
RELPRIME = {<x,y> | x e y sono primi tra loro}

Per dimostrare che RELPRIME appartiene a P dobbiamo trovare una MdT deterministica che lo risolva in tempo polinomiale. Iniziamo a scrivere una MdT che calcoli il divisore maggiore dati due interi x e y:

Facciamo un esempio di risoluzione. Dati in ingresso x=24 e y=18:
(1)

(1) y=0? NO

(1) y=0? SÌ
(4) output: 6

Creiamo ora una seconda MdT che usa E come sub-routine:

Per fare l'analisi dell'algoritmo E, consideriamo due casi:

• se (x/2) >= y, dato che (x mod y) < y, avremo che:

• se (x/2) < y, dato che (x mod y) = x - y, avremo che:

In entrambi i casi avremo che ad ogni passata del ciclo il valore della x viene come minimo dimezzato. Quindi il numero massimo di volte in cui vengono ciclati i passi (2) e (3) di E è il valore più piccolo tra 2logx e 2logy. Essendoci di messo un logaritmo il numero di passi è sicuramente polinomiale, ed essendo ogni operazione di complessità polinomiale il problema RELPRIME è sicuramente in P.

Teorema 3 - sui linguaggi liberi dal contesto

Dimostrazione

Sappiamo già dalle lezioni precedenti che i linguaggi liberi dal contesto (da ora CFL) sono decidibili, perché è possibile creare un algoritmo che lo decida. Dobbiamo quindi dimostrare che tale algoritmo viene eseguito in tempo polinomiale. Dov'è la fregatura? Che la dimostrazione della decidibilità di un CFL L tirava in ballo il fatto che era stato generato da una grammatica libera dal contesto G espressa nella forma normale di Chomsky, e che bisognava verificare tutte le derivazioni di G per vedere se una certa stringa di L poteva essere accettata. Il numero di derivazioni è però esponenziale, quindi dobbiamo scegliere un'altra strada per dimostrare il nostro teorema.

Chi di noi non stava pensando alla programmazione dinamica come soluzione? Esatto.
Nella programmazione dinamica si cercano e si utilizzano le soluzioni di sottoproblemi per risolvere il problema principale. Nel nostro caso i sottoproblemi sono le sottostringhe generate per scomposizione dall'originale stringa w generata da G, e dovremo verificare che ognuna di esse possa essere derivata a partire dalle variabili della grammatica. Per fare ciò costruiremo una tabella n x n, con coordinate i e j. In ogni cella (i,j) con i<=j potrò trovare tutte le variabili che mi permettono di generare la sottostringa w_iw_i+1...w_j; al contrario tutte le celle con i>j rimarranno inutilizzate. Grazie ai principi della programmazione dinamica useremo via via le soluzioni ottenute per le sottostringhe precedenti. Come? Quando andando avanti con la risoluzione scopro che posso generare una data (i,j) utilizzando una sottostringa già risolta, metto nella cella quella sottostringa. Come? Ogni sottostringa di lunghezza k+1 può essere divisa in k modi possibili (ad esempio w₁w₂w₃w₄ può essere divisa in: w₁|w₂w₃w₄, w₁w₂|w₃w₄, w₁w₂w₃|w₄). Per riutilizzare le informazioni già messe in tabella basterà cercare nella mia grammatica una regola A->BC dove B mi permette di generare la parte sinistra e C la destra.
Ed ora, vediamo la MdT D che fa tutto questo (con "subs" si intenderà "sottostringa"):

In altre parole, se nell'ultima colonna della prima riga ci ritroviamo la variabile iniziale S l'algoritmo ha successo. Via quelle sopracciglia alzate, facciamo piuttosto l'analisi dell'algoritmo considerando i passaggi più critici:

• (4) e (5) possono essere ripetuti al più n*v volte, dove v è il numero di variabili della grammatica. Dato che v è comunque una costante (non dipende dalla n), entrambi i passi hanno complessità O(n);
• (6) può essere svolto al più n volte, quindi è O(n);
• (7) viene ripetuto al più n volte tutte le volte che viene eseguito (6), quindi avrà complessità O(n)*n =O(n²);
• (8) e (9) vengono ripetuti al più n volte tutte le volte che viene eseguito (7), quindi avranno complessità O(n²)*n =O(n³);
• (10) e quindi (11) vengono eseguiti ogni volta che partono (8) e (9), e vengono ripetuti r volte, dove r è il numero di regole. Avranno quindi complessità O(n³)*r=O(n³) (perché r è costante).

La complessità totale dell'algoritmo sarà dunque O(n)+O(n³)=O(n³), che è meravigliosamente polinomiale. Quindi abbiamo dimostrato che ogni linguaggio libero dal contesto è in P.

Torna alla pagina di Informatica Teorica