Che cosa significa complesso? nel linguaggio comune un problema complesso è un problema che ha bisogno di molte risorse per essere risolto (tempo, energie, impegno…). Nell’informatica invece la complessità ha una definizione precisa, che ha un impatto enorme sulle nostre vite.
Anzitutto, non esistono problemi complessi, esistono soluzioni complesse. Se cento anni fa avessimo voluto sapere la strada più breve per andare da Roma a Parigi a piedi, ci sarebbero voluti giorni di ricerca, oggi bastano pochi minuti su Google. La complessità è quindi una caratteristica del modo migliore che conosciamo per risolvere un problema, non del problema in sé: solo per estensione si parla di complessità di un problema. È una distinzione importante perché la complessità cambia nel tempo a seconda degli strumenti che abbiamo per risolvere il problema.
In informatica una soluzione è un algoritmo, cioè una sequenza di istruzioni non ambigue che serve a risolvere una classe di problemi e, nell’accezione più comune, calcolarne la complessità computazionale significa fare una stima di quanto tempo occorre per risolvere il più sfortunato dei problemi in quella classe. Facciamo un esempio, immaginiamo di avere una lista di numeri interi lunga 10 elementi, non ordinati, il problema da risolvere consiste nel decidere se il numero 8 è nella lista. Il nostro algoritmo fa una ricerca sequenziale, ovvero parte dal primo elemento, controlla se è uguale ad 8, in caso affermativo si ferma, altrimenti si sposta all’elemento successivo e così via, fino a quando trova il numero 8 oppure arriva alla fine della lista. Calcolare la complessità significa provare a predire il numero di istruzioni che devono essere eseguite per risolvere il problema (al netto di costanti moltiplicative o additive che non ci interessano), perché assumiamo che il tempo che ci vuole sia proporzionale a questo numero.
Se siamo fortunati, 8 è il primo numero della lista e ci vuole una sola operazione di controllo, se siamo sfortunati, dobbiamo scorrere tutta la lista e ce ne vogliono 10. Il numero esatto di operazioni quindi dipende dalla dimensione dei dati in ingresso e dalla fortuna. Eliminiamo il secondo fattore, generalizziamo a una lista di dimensione N e mettiamoci nel caso peggiore: l’elemento cercato non è nella lista. Allora ci vorranno N operazioni, quindi la complessità dell’algoritmo aumenta linearmente con N. Significa che se ci vuole un secondo a risolvere il problema con una lista di 1000 elementi, ci aspettiamo che ce ne vogliano al massimo due per una lista di 2000 elementi. La complessità computazionale di un algoritmo è quindi una stima di quante istruzioni ci vogliono per risolvere il caso peggiore, al crescere della dimensione del problema N, ed è interessante per valori di N grandi.
Gli algoritmi si dividono in due grandi famiglie, quelli con complessità polinomiale (numero di istruzioni che sarà al massimo Nk, per un dato valore di k) e quelli non polinomiali (complessità esponenziale, fattoriale ecc…). I primi sono quelli che abbiamo speranza di risolvere, anche con N grande. I secondi sono quelli che non vale neanche la pena di provare a risolvere esattamente se N è abbastanza grande, e dobbiamo quindi ricorrere a soluzioni approssimate. Gli algoritmisti cercano di migliorare gli algoritmi (per diminuire la complessità) oppure cercano algoritmi diversi che non trovano la soluzione esatta ma trovano approssimazioni sempre migliori (chiamate euristiche).
Un aspetto affascinante della complessità è che ci sono alcune cose che possiamo fare solo perché ce ne sono altre impossibili. È il caso della crittografia, che usiamo tutti i giorni quando navighiamo su Internet. Con la crittografia, solo chi possiede una certa chiave può accedere ai dati che inviamo o riceviamo. In realtà, non esiste un motivo teorico per cui qualcuno che intercetta il nostro traffico non possa decifrarlo pur senza sapere la chiave. Semplicemente, il miglior algoritmo che conosciamo per rompere una cifratura moderna ha una complessità computazionale così alta che riteniamo che sia computazionalmente impossibile, ovvero, che con i computer attuali non si possa fare. Ma sappiamo che la complessità è una proprietà della soluzione, non del problema, se qualcuno domani dovesse scoprire un algoritmo che risolve lo stesso problema con complessità polinomiale, la crittografia che utilizziamo sarebbe sconfitta. Oppure, se qualcuno avesse accesso a una tecnologia del tutto nuova, che cambia il modo in cui modelliamo la complessità (ad esempio, un computer quantistico), di nuovo, la crittografia attuale non sarebbe in gran parte più utile. Infine, anche senza che si verifichino gli scenari precedenti, se qualcuno riuscisse ad accumulare una potenza di calcolo a oggi inimmaginabile, potrebbe decifrare alcuni dati anche senza conoscere la chiave.
È quindi molto importante che matematici, crittografi e informatici continuino a lavorare pubblicamente per migliorare gli algoritmi e capire quando alcuni danno segni di debolezza richiedendo l’uso di chiavi più lunghe o nuove funzioni crittografiche.