10. Complessità temporale

In questo parleremo della complessità temporale partendo dalle sue basi. Anche se un problema risulta decidibile, questo può anche non essere risolvibile a causa di una quantità di tempo o di memoria impiegati nella sua risoluzione. La prima misura fondamentale è il tempo di esecuzione o complessità di tempo, della quale diamo una definizione facendo riferimento a una macchina di Turing deterministica M che si ferma su tutti gli input. Questa misura può essere espressa come funzione f : $N \longrightarrow N$, dove f(n) è il numero massimo di passi che M utilizza su un qualsiasi input di lunghezza n. Se f(n) è il tempo di esecuzione di M, diciamo che M ha tempo di esecuzione f(n) e che M è una macchina di Turing di tempo f(n).

Quindi possiamo dire che il tempo di esecuzione di un algoritmo è espresso tramite un'espressione complessa, di cui ci si limita ad una stima. Un metodo di stima comunemente utilizzato è l'analisi asintotica, mediante il quale si valuta il tempo di esecuzione dell'algoritmo quando viene eseguito su grandi input. In questa analisi si prende in considerazione solo il termine di ordine maggiore dell'espressione del tempo di esecuzione dell'algoritmo, trascurandone il suo coefficiente e tutti i termini di ordine inferiore, perchè il termine di ordine più alto domina gli altri termini quando l'input è grande. Questa notazione prende il nome di notazione asintotica o notazione O-grande. Prendendo in considerazione $R^+$ come insieme dei numeri reali non negativi, definiamo le funzioni f e g nel seguente modo: "f,g : $N \longrightarrow R^+$." Si dice che f(n)=O(g(n)) se esistono interi positivi c e $n_0$ tali che per ogni $n \geq n_0$, $f(n) \leq c g(n)$. Quando f(n) = O(g(n)), diciamo che g(n) è un limite superiore per f(n), o più precisamente g(n) è un limite superiore asintotico per f(n). Notiamo che in questa fase stiamo ignorando le costanti.

La notazione O-grande appare anche in espressioni aritmetiche, nelle quali ogni occorrenza del simbolo O rappresenta un diverso fattore costante nascosto. Vi sono alcune espressioni esponenziali, nelle quali si possono individuare dei limiti esponenziali o dei limiti polinomiali. Questa notazione esprime che una funzione è asintoticamente non più grande di un'altra. Vi è anche un'altra notazione definita notazione o-piccolo, che esprime il concetto di funzione asintoticamente più piccola rispetto ad un'altra. Per definire quest'ultima notazione, possiamo definirla come:

Definizione notazione o-piccola

Siano f e g funzioni definite come "f,g : $N \longrightarrow R^+$". diciamo che f(n)=o(g(n)) se $\lim_{n \to \infty} {f(n) \over g(n)} = 0$. In altri termini, f(n) = o(g(n)) significa che per ogni numero reale c > 0, esiste un numero $n_0$, tale che f(n) < c g(n) per ogni $n \geq n_0$

Definiamo ora altri concetti fondamentali per comprendere meglio la complessità temporale. In genere si indica con il termine classe di complessità di tempo, TIME(t(n)), l'insieme di tutti i linguaggi che sono decisi da una macchina di Turing in tempo O(t(n)), mentre la funzione f(n) mediante la quale si indica il numero massimo di passi che N usa per ognuna delle computazioni su ogni input di lunghezza n, prende il nome di funzione di esecuzione di N. Esistono principalmente due classi all'interno della complessità temporale, la classe polinomiale, indicata con P, e la classe non polinomiale, indicata con NP. Nella programmazione differenze polinomiale nel tempo di esecuzione sono considerate piccole, mentre differenze esponenziali sono considerate grandi. Questo perchè vi è una differenza notevole tra il tasso di crescita di polinomi e il tasso di crescita di un esponenziale.

Infatti algoritmi aventi tempo polinomiale sono abbastanza veloci, a differenza di quelli esponenziali. Algoritmi aventi tempo esponenziale sono molto utili quando bisogna risolvere problemi mediante una ricerca esaustiva nello spazio delle soluzioni, la quale prende il nome di ricerca mediante forza bruta. Tutti i modelli computazionali deterministici ragionevoli sono invece polinomialmente equivalenti, ovvero uno di essi può simulare un altro con un aumento solo polinomiale del tempo di esecuzione. Dopo aver fatto queste premesse possiamo dare una definizione formale della classe polinomia P.

Definizione della classe polinomiale P

P è la classe di linguaggi che sono decidibili in tempo polinomiale su una macchina di Turing deterministica a singolo nastro. Ovvero la classe P è la classe in cui vale la seguente formula: P = $\cup_k TIME ( n^k )$

La classe P ha un ruolo fondamenta nella teoria della complessità temporale per due semplici motivi:

• P è invariante per tutti i modelli di calcolo che sono polinomialmente equivalenti ad una macchina di Turing deterministica a nastro singolo
• P corrisponde approssimativamente alla classe dei problemi che sono realisticamente risolvibili su un computer.

L'altra classe di problemi che abbiamo tralasciato è la classe NP, della quale ci apprestiamo ora a dare una definizione.

Definizione della classe polinomiale NP

NP è la classe di linguaggi che ammettono un verificatore in tempo polinomiale.

Il termine NP deriva da tempo polinomiale non deterministico e deriva da una caratterizzazione alternativa che utilizza le macchine di Turing non deterministiche di tempo polinomiale. Nella definizione abbiamo parlato di verificatore, senza però darne una definizione, cosa che ci apprestiamo a fare ora.

Definizione di verificatore

Un verificatore per un linguaggio A è un algoritmo V, dove A = { w | V accetta < w, c > per qualche stringa c }. Il tempo di un verificatore si misura solo in termini della lunghezza di w, quindi un verificatore in tempo polinomiale viene eseguito in tempo polinomiale nella lunghezza di w. Un linguaggio A è polinomialmente verificabile se ammette un verificatore in tempo polinomiale.

In modo analogo alla classe di tempo deterministico TIME ( t ( n ) ), definiamo la classe di complessità di tempo non deterministico NTIME ( t ( n ) ).

Definizione di NTIME ( t ( n ) )

NTIME ( t ( n ) ) = { L | L è un linguaggio deciso da una macchina di Turing non deterministica di tempo O ( t ( n ) ) }.

La classe NP è una classe indifferente alla scelta di un modello computazionale ragionevole non deterministico, in quanto tutti questi modelli sono polinominalmente equivalenti. Si utilizzano le stesse convenzioni per gli algoritmi di tempo polinomiale deterministici per descrivere e analizzare algoritmi non deterministici aventi tempo polinomiale. Ogni fase di un algoritmo non deterministico di tempo polinomiale deve avere una chiara implementazione in un tempo polinomiale non deterministico su un modello di calcolo non deterministico ragionevole.

Esiste anche una terza classe denominata NP-completi, classe che è stata identificata da Cook e Levin, i quali scoprirono che vari problemi appartenenti a NP, la cui complessità individuale è correlata a quella dell'intera classe. Se un qualsiasi problema appartenente a NP richiede tempo più che polinomiale, lo stesso vale per un NP-completo. La classe NP-completa può prevenire la perdita di tempo relativa alla ricerca di algoritmi di tempo polinomiale inesistenti per risolvere un problema particolare.

Un esempio di problema NP-completo è il problema della soddisfacibilità, la cui descrizione viene tralasciata per definire altri aspetti più importanti, uno tra tanti la riducibilità in tempo polinomiale. Quando un problema A è riducibile efficientemente al problema B, una soluzione efficiente per B può essere usata per risolvere A eficientemente. Diamo due definizioni importanti:

Definizione di funzione calcolabile in tempo polinomiale

Una funzione calcolabile in tempo polinomiale è una funzione f; $\sum^* \longrightarrow \sum^*$, se esiste una macchina di Turing di tempo polinomiale M che arresta con f ( w ) soltanto sul suo nastro, quando ha iniziato con un qualsiasi input w.

Definizione di riducibilità in tempo polinomiale

Il linguaggio A è riducibile mediante funzione in tempo polinomiale, o semplicemente riducibile in tempo polinomiale, al linguaggio B, se esiste una funzione calcolabile in tempo polinomiale f: $\sum^* \longrightarrow \sum^*$ dove, per ogni w,$w \in A \iff f(w) \in B$. Allora la funzione f è chiamata riduzione di tempo polinomiale di A a B.

La riducibilità in tempo polinomiale è l'analogo efficiente della riducibilità mediante funzione. Vi sono altre forme di riducibilità efficiente, ma la riducibilità in tempo polinomiale è una forma semplice. Dopo aver fatto questo piccolo preambolo diamo però la definizione di NP-completo.

Definizione di NP-completo

Un linguaggio B è NP-completo se soddisfa due condizioni:

• B appartiene a NP
• ogni A apaprtenente a NP è riducibile in tempo polinomiale a B
.

Prima di introdurre il teorema di Cook Levin, dobbiamo discutere di un caso speciale di problema di soddisfacibilità per cui tutte le formule sono una forma speciale, questo problema prende il nome di 3SAT. Definiamo un letterale è una variabile booleana o una variabile boolean negata, una clausola consiste in diversi letterali connessi tramite operatori. Una formula booleana è in forma normale congiuntiva, definita anche formula cnf, se comprende diverse clausole connesse tramite operatori. Quindi possiamo definire 3SAT come { < $\phi$ | $\phi$ è una formula 3cnf soddisfacibile }. Il teorema di Cook-Levin enuncia:

Teorema Cook-Levin

SAT è un NP-completo.

Per dimostrare questo teorema si deve dimostrare inizialmente che SAT appartiene a NP, per poi dimostrare che qualsiasi linguaggio che appartiene a NP è riducibile in tempo polinomiale a SAT. Quest'ultima dimostrazione può essere condotta attraverso una riduzione di tempo polinomiale per ciascun linguaggio A appartenente a NP a SAT.