La complessità computazionale è un concetto che quantifica la necessità di risorse computazionali per l'esecuzione di un dato algoritmo, affinché esso venga eseguito completamente.
Essa viene spesso rappresentata tramite la notazione a simboli di Landau, come la notazione grande O (big O), omega ecc. È importante non confondersi quando si legge una simile notazione, in quanto essa può trarre in inganno, specialmente gli inesperti.
O(n²) descrive il comportamento asintotico della funzione che mette in relazione la molteplicità dell'input (quanto è grande) con la molteplicità dei passaggi (quanti step computazionali devono essere eseguiti). Ciò significa che se raddoppio l'input, mi devo aspettare un quadruplicarsi del numero di passaggi da eseguire. Un semplicissimo algoritmo che presenta tale complessità è ad esempio quello che genera una matrice NxN dato un certo numero N in input. Se dovessimo fornire N = 3, allora l'algoritmo dovrà generare una matrice 3x3, che presenta 9 elementi. Dunque l'algoritmo eseguirà 9 step, prima di fermarsi. Se dovessimo invece fornire N = 6, l'algoritmo eseguirà 36 step. Ma attenzione. Ciò non significa che sia davvero così. Nella descrizione dell'andamento asintotico vengono meno fattori di proporzionalità, ovvero O(cn²) con c costante rispetto all'input è di fatto scritto come O(n²).
Come accennato prima, esistono diversi simboli, ad esempio Ω e Θ, che possiedono altre definizioni. Possiamo considerare O come "il caso peggiore", che in realtà corrisponde tipicamente alla vera complessità di un algoritmo, dato che si assume sempre il caso pessimo.
Vediamo le definizioni formali di questi costrutti:
- O grande
Siano 𝑓 e 𝑔 due funzioni definite da ℕ in ℝ.
Si dice che 𝑓(𝑛) è O grande di 𝑔(𝑛) se ∃𝑐 > 0, 𝑛0 ∈ ℕ: ∀𝑛 ≥ 𝑛0, |𝑓(𝑛)| ≤ 𝑐|𝑔(𝑛)|
Si dice anche che 𝑓(𝑛) ha ordine di grandezza minore o uguale a quello di 𝑔(𝑛), cioè la funzione 𝑔(𝑛) “domina” 𝑓(𝑛)
- o piccolo
Si dice che 𝑓(𝑛) è un o piccolo di 𝑔(𝑛) se ∀𝑐 > 0∃𝑛0 > 0: 0 ≤ 𝑓(𝑛) < 𝑐𝑔(𝑛), ∀𝑛 ≥ 𝑛0.
- Omega grande
Si dice che 𝑓(𝑛) è omega grande di 𝑔(𝑛) se ∃𝑐 > 0, 𝑛0 ∈ ℕ: ∀𝑛 ≥ 𝑛0, |𝑓(𝑛)| ≥ 𝑐|𝑔(𝑛)|, ∀𝑛 ≥ 𝑛0.
- omega piccolo
Si dice che 𝑓(𝑛) è omega piccolo di 𝑔(𝑛) se 𝜔(𝑔(𝑛)) = ∀𝑐 > 0 ∃𝑛0 > 0: 0 ≤ 𝑐𝑔(𝑛) < 𝑓(𝑛), ∀𝑛 ≥ 𝑛0
- Theta
Le funzioni 𝑓(𝑛) e 𝑔(𝑛) sono dette avere lo stesso ordine di grandezza, espresso in simboli 𝑓(𝑛) = Θ(𝑔(𝑛))
Se ∃𝑐1,c2 > 0, 𝑛0 ∈ ℕ: ∀𝑛 ≥ 𝑛0, 𝑐1|𝑔(𝑛)| ≤ |𝑓(𝑛)| ≤ 𝑐2|𝑔(𝑛)|.
Valgono le seguenti proprietà:
1. 𝑓 = 𝑂(𝑔) ⟺ 𝑔 = Ω(𝑓).
2. 𝑓 = 𝑜(𝑔) ⟺ 𝑔 = 𝜔(𝑓).
3. 𝑓 = 𝑂(𝑓).
4. 𝑓 = 𝑜(𝑓) ⇒ 𝑓 ≡ 0.
Valgono inoltre le seguenti implicazioni:
1. 𝑔 = 𝑜(𝑓) ⇒ 𝑔 = 𝑂(𝑓). Vale a dire 𝑜(𝑓) ⊆ 𝑂(𝑓).
2. 𝑓 = 𝑂(𝑔) ⇏ 𝑓 = 𝑜(𝑔).
Vale inoltre la proprietà transitiva in ognuna delle notazioni, ad esempio, se 𝑓 = 𝑂(𝑔) e 𝑔 = 𝑂(ℎ)
allora si avrà 𝑓 = 𝑂(ℎ).
È facile notare come un algoritmo di una tale complessità sia oneroso e inauspicabile come soluzione a problemi ricorrenti. Infatti, sono presenti numerosi problemi computazionali che possono scendere ben al di sotto di tale andamento asintotico. Le complessità computazionali più comuni sono (in ordine dall'asintoticamente più lento al più veloce):
- O(1) complessità costante (restituire il primo elemento di un array)
- O(log n) complessità logaritmica (ricerca in una BST bilanciata)
- O(√n) complessità radice di n (decomposizione in radice dei "range query problems")
- O(n) complessità lineare (ricerca di un elemento in un array non ordinato)
- O(n log n) complessità linearitmica (lower bound di qualsiasi algoritmo di ordinamento basato su confronto)
- O(n²) complessità quadratica (moltiplicazione di matrici booleane)
- O(n^k) complessità più che quadratica (problema della cricca)
- O(2^n) complessità esponenziale (solutore SAT)
- O(n!) complessità fattoriale (problema del commesso viaggiatore)
Una classe di complessità è un insieme di problemi tale che, se esiste una soluzione data da una macchina di Turing (o Turing-equivalente) M, possono essere risolti usando O(𝑓(𝑛)) della risorsa R, con dimensione n dell'input.
Le classi di complessità sono moltissime e hanno relazioni spesso non note o indimostrate. Esiste una branca dell'informatica (appunto chiamata Teoria della Complessità) che si occupa di studiare questi insiemi.
Di seguito una breve schematizzazione:
- Problemi di decisione -> Tipo 0 (recursively-enumerable)
- Problemi di decisione -> Indecidibili (vicolo cieco)
- Tipo 0 (recursively-enumerable) -> Decidibile
- Decidibile -?> EXPSPACE -?> EXPTIME -?> PSPACE
- PSPACE -> Tipo 1 (context-sensitive) -> Tipo 2 (context-free) -> Tipo 3 (regular)
- PSPACE -> NC -> Tipo 2 (context-free)
- PSPACE -?> Co-NP -?>
- PSPACE -?> BPP -?> P
- PSPACE -?> NP -?> BQP -?> P
- PSPACE -?> NP -?> NP-Completi
- PSPACE -?> PSPACE-Completi
- P -?> NC
- P -?> P-Completi
Nota: la freccia ha un punto interrogativo al centro se la validità di relazione di sottoinsieme proprio è solo congetturata
Ad ogni modo, nel 99% dei casi, si ha a che fare con problemi P o NP, o comunque ciò è quello che importa.
La classe NP è l'insieme dei problemi di decisione che possono essere risolti da una macchina di Turing non deterministica in tempo polinomiale, mentre la classe P è l'insieme dei problemi di decisione che possono essere risolti da una macchina di Turing deterministica in tempo polinomiale. In altre parole, in un problema P è "sbrigativo" sia trovare una soluzione, che verificare che un possible risultato sia una soluzione. In un problema NP, non è così facile trovare una soluzione, ma verificare che una soluzione sia corretta è altrettanto facile. Si pensi ad un lucchetto con un insieme enorme di combinazioni, trovare il codice che lo apre è straordinariamente dispendioso, ma verificare una qualsiasi sequenza è banale. Esistono inoltre classi di problemi in cui non solo è difficile trovare la soluzione, ma è altrettanto difficile capire se la soluzione è corretta.
Esiste un'importantissima congettura sulla possibilità che P=NP, e risolverla modificherebbe permanentemente la nostra comprensione della teoria e ci permetterebbe di arrivare a delle conclusioni dalle implicazioni profondissime, ad esempio che qualsiasi problema di ottimizzazione fortemente NP-difficile con una funzione obiettivo limitata polinomialmente non può avere un FPTAS (approssimazione polinomiale) a meno che P=NP. In palio è prevista una ricompensa di un milione di dollari per chi riuscirà a trovare la risposta.
Esistono congetture ancora più forti, come la congettura SETH (Strong Exponential Time Hypothesis), o la OVC (congettura del vettore ortogonale).
Ma vediamo un problema con un conditional bound (cioé un limite che può essere superato solo se si trova la dimostrazione che SETH è falsa)
Il diametro di un grafo è la più grande distanza tra qualsiasi paio di nodi. Può anche essere definito come il massimo tra tutte le eccentricità. È una metrica assai utile, usata in tante applicazioni (nei social network si usa per calcolare la distanza tra qualsiasi paio di persone, ad esempio, come mostrato da Milgram)
Come calcolarla? In realtà è semplice, basta applicare una serie di BFS proporzionali al numero di nodi per ottenere una complessità quadratica O(nm) e dunque ascrivibile a O(n²). In alternativa, con uguale complessità, potremmo usare l'algoritmo di Dijkstra, nel caso di grafi pesati (in tal caso non potrebbero esserci cicli negativi, ovviamente)
In ogni caso, abbiamo visto che entrambe soluzioni scalano quadraticamente, e usare un tale approccio in un grafo reale (ad esempio il grafo che rappresenta le interconnessioni di tutte le persone in un social media, enorme in dimensione e molto sparso) sarebbe follemente dispendioso e possibile solo formalmente.
Certamente non possiamo eseguire algoritmi quaratici in applicazioni reali. È congetturato che non è possibile risolvere questo problema in O(n^(2-ε)) con ε > 0 (qui entra il gioco SETH)
Se SETH è falsa, deve esistere un algoritmo in grado di completare questo procedimento con un andamento esponenziale meno che quadratico, cosa indimostrata. Ad oggi, il meglio che possiamo fare è adoperare algoritmi di approssimazione o euristiche convenienti.
Prima di proseguire, approfondiamo cosa sia SETH.
SETH è una famosa congettura formalizzata da Impagliazzo e Paturi nel 1999. Essa afferma che la soddisfacibilità delle formule booleane in k-CNF non può essere risolta in tempo subesponenziale.
Forse questo sembrerà poco collegato con il diametro di un grafo, ma in realtà possiamo ridurre il problema di soddisfacibilità esattamente al trovare il diametro di un grafo.
Effettuiamo una costruzione che prende una formula booleana in forma normale congiuntiva (CNF) e creiamo un grafo che "codifica" se la formula F è soddisfacibile. Suddividiamo in due le variabili e formiamo un grafo che ha una metà dei nodi a sinistra e l'altra metà a destra. Al centro saranno collocati dei nodi clausola, più dei nodi dummy per garantire un grafo connesso. Formiamo un arco tra due nodi passando per i nodi clausola se l'assegnazione produce un'assegnazione falsa (non soddisfatta). Se F è insoddisfacibile, allora deve esistere almeno una clausola violata da tutte le assegnazioni, ragione per cui esisterà un nodo centrale da cui è possibile passare da un lato all'altro. Il risultato è un grafo di diametro 2. Se F è soddisfacibile, deve esistere almeno un'assegnazione delle variabili che soddisfi tutte le clausole. Questo comporta una mancanza di archi passanti per i nodi clausola, in tal caso si fanno passare attraverso i nodi dummy, che sono sempre due. Questo comporta un grafo di diametro 3.
Come possiamo vedere, abbiamo ridotto il problema SAT in un problema di diametro, per cui le due classi di complessità coincidono. Risolvere un problema significa implicare che esiste una soluzione che risolve anche l'altro problema.
Supponiamo di avere un algoritmo che risolve il problema 2 vs 3 in O(n^(2-ε)), ε > 0
Data una qualsiasi formula F possiamo costruire un grafo con l'approccio mostrato. Decidiamo se il diametro ha valore 2 o 3 con la complessità di sopra
O(n^(2-ε)) = O(2^[(n/2)(2-ε)]) = O(2^[(2-ε)/2]) = O(2^(γn)) dove γ = ((2-ε)/2) e ovviamente γ < 1.
Dunque, date le premesse abbiamo risolto SAT in tempo subesponenziale e quindi confutato la SETH, eliminando il lower bound.
Fintantoché tale algoritmo non viene trovato, la SETH regge.
Ragioniamo ora su possibili soluzioni tramite 1. euristiche e 2. randomizzazione
L'algoritmo di 2-sweep è un algoritmo euristico che opera in tempo O(n+m), e il meccanismo è il seguente:
- Scegliamo v ∈ V campionando uniformemente (scelta casuale)
- Troviamo un nodo che chiamiamo a, che è l'ultimo nodo visitato dalla BFS da v
- Troviamo un nodo che chiamiamo b, che è l'ultimo nodo visitato dalla BFS da a
- La stima del diametro è data dalla distanza tra a e b, che è un lower bound di D
In essenza, stiamo solo considerando due BFS!
Per quanto l'algoritmo possa sembrare di travolgente banalità, per la verità è incredibilmente efficace. Vediamo perché.
- Nell'aggiornamento del lower bound consideriamo max{L, d(r,a), d(a,b)} ≤ D (ovvio, ogni BFS è un lower bound di D)
- Nell'aggiornamento dell'upper bound consderiamo min{U, 2d(r,a), 2d(a,b)} ≥ D per disuguaglianza triangolare
È una 2-approssimazione, D ≤ 2 BFS(x), x ∈ V
Vediamo ora di risolvere lo stesso problema tramite randomizzazione, che ci dà una stima D' con un minimo di garanzia, non dovrebbe discostarsi troppo (quantificheremo dopo) da D.
- Idealmente, per qualsiasi 0 < β < 1, vorremmo avere (1-β)D ≤ D' ≤ D
- Se fosse possibile, confuterebbe SETH
- Il meglio che possiamo fare è (1-β) = 2/3
Perché un numero così specifico? Non è difficile risalire al perché:
Se D = 3, per (1-β) > 2/3 allora D' ≥ (1-β)3 -> D' > 2, concludendo che la formula è soddisfacibile, confutando SETH!
Con questo fatto in mente, possiamo formulare un algoritmo che segue questa approssimazione garantita in tempo meno che quadratico (O(n √n log n) nello specifico)
L'algoritmo è quanto segue:
1. Campioniamo uniformemente S = α n/k log n nodi, con α > 1 costante e k = √n.
- Perché tale campionamento? Perché in grafi sparsi (e quindi di configurazione realistica) questo numero di campionamenti dà un'alta probabilità di includere almeno un nodo di alta eccentricità (vedremo dopo il perché)
2. BFS(S) per trovare ω, il nodo più distante da S
3. Ritorniamo la massima eccentricità trovata in Z dove Z è l'insieme S ∪ Nk(ω), dove Nk sono i primi k nodi della BFS
Vediamo il tempo totale:
1. O(|S|) = O(n/k log n)
2. O(n)
3. O(|Z|n) = O((n/k log n +k)n)
Risultato: O(n √n log n), esattamente il risultato menzionato all'inizio.
Ma perché funziona?
Vediamo le ragioni:
1. S è un hitting set for qualsiasi Nk(u), u ∈ V con alta probabilità
2. Infatti, P[S ∧ Nk(u) = ∅] = ((n-k)/n)^|S| = (1-k/n)^|S| = e^(-k/n)^|S| = e^(α log n) = 1/n^α
3. D' è entro i bound e quindi non viola SETH, né sovrastima