Nona puntata del nostro viaggio
Abbiamo visto nel post precedente che per alcune elaborazioni non è possibile trovare alcun algoritmo. In aggiunta, dal momento che siamo mortali e non abbiamo a disposizione un tempo infinito per ottenere una risposta, ci interessa anche sapere quanto tempo può metterci un certo algoritmo a completare la sua elaborazione.
In prima istanza ci interessa distinguere quei problemi, chiamati trattabili, in cui man mano che il problema cresce di dimensione continuiamo a dover aspettare un tempo “umano” per la risposta, e quei problemi, detti invece intrattabili, in cui questo non accade. Invece di parlare di tempo, discuterò questi aspetti facendo riferimento al numero di passi necessario per risolvere il problema da parte del miglior algoritmo noto per esso. Il motivo di questa scelta è che il tempo può dipendere dalla velocità intrinseca dello specifico calcolatore usato per l’esecuzione del (programma che concretizza) l’algoritmo, mentre noi siamo interessati a una caratterizzazione indipendente dalle evoluzioni tecnologiche. In ogni caso, i risultati in termini di trattabilità o intrattabilità non cambiano. Viceversa, ma non ne parleremo in questi post e vi rimando al libro La rivoluzione informatica per una discussione, l’utilizzo di computer quantistici rende trattabili alcuni dei problemi che sono intrattabili usando un computer classico (che è un automa equivalente alla MUT).
Ogni algoritmo, una volta espresso in un programma, richiede un tempo proporzionale al numero delle istruzioni che devono essere eseguite. Dato quindi l’algoritmo, si può scrivere la funzione matematica, detta funzione di complessità dell’algoritmo, che esprime questo numero in base alla dimensione N del problema. Dovremmo ricordare tutti, per averla studiata a scuola, la differenza tra una funzione polinomiale e una funzione esponenziale. Nella prima, l’argomento N è la base di una potenza (p.es. N2 oppure N3 o anche N10), mentre nella seconda è l’esponente della potenza (p.es. 2N oppure 3N o anche 10N). Le funzioni esponenziali crescono molto più velocemente di quelle polinomiali. Nella tabella seguente riportiamo il valore di queste funzioni per differenti valori dell’argomento N. Ricordiamo che il simbolo “ ~ ” vuol dire “circa”, “approssimativamente”, e che la notazione, ad esempio, 1010 indica la cifra 1 seguita da 10 zeri, cioè il valore 10 miliardi. Nella tabella si vede che già per N=60, tutte le funzioni esponenziali presentate hanno valore maggiore di tutte le funzioni polinomiali.
È importante ricordare che la funzione di complessità viene espressa, per ogni algoritmo, in riferimento al cosiddetto “caso pessimo” per l’esecuzione dell’algoritmo stesso, ovvero a quello più sfavorevole in termini di numero di istruzioni da eseguire (assumendo, per semplicità, che tutte le istruzioni richiedano uno stesso tempo). Consideriamo il primo dei problemi presentati nel post precedente, quello dell’ordinamento. Vogliamo sapere quale sia il tempo massimo garantito di esecuzione dell’algoritmo in funzione della quantità N, qualunque cosa possa accadere con gli N dati in ingresso. Si può dimostrare che per questo problema il miglior algoritmo conosciuto garantisce un tempo proporzionale a N⋅log(N ), dove “log” è la funzione logaritmica che dovremmo ricordarci dalle scuole superiori, e questo risultato non è migliorabile.
Assumiamo ora che l’esecuzione di una singola istruzione richieda a un moderno computer un nanosecondo, cioè un miliardesimo di secondo. In formula, 10-9 (cioè 1/109) secondi. Consideriamo poi il secondo problema, dei cammini minimi, per il quale il miglior algoritmo garantisce nel caso pessimo l’esecuzione di al più N3 istruzioni per una lista con N città (trascurando miglioramenti marginali ottenuti negli ultimi anni). Allora siamo in grado di risolverlo per 100 città in un millesimo di secondo (perché 1.000.000, cioè 106, moltiplicato per 10-9 fa 10-3, cioè 1/103 = 0,001) e per 1.000 città in un secondo (1.0003 = 109, che moltiplicato per 10-9 fa esattamente 1). Se avessimo poi bisogno di risolverlo per 10.000 città, servirebbero 1.000 secondi, ovvero circa 17 minuti. Per 100.000 città sarebbe addirittura necessario un milione di secondi, pari a circa 12 giorni: un tempo molto lungo, ma tutto sommato accettabile.
Vediamo invece cosa accade per il terzo problema, del commesso viaggiatore, per il quale i migliori algoritmi conosciuti richiedono l’esecuzione di 2N istruzioni per una lista con N città. In questo caso potremmo risolverlo per 20 città in appena più di un millesimo di secondo, ma già per 30 città sarebbe necessario un secondo, 40 città richiederebbero 17 minuti, e 50 sarebbe il massimo numero di città per cui il problema è risolvibile aspettando un tempo di 12 giorni. La risoluzione per 60 città potrebbe essere ottenuta in circa 32 anni, chiaramente un tempo inaccettabile.
Ecco quindi che la distinzione tra problemi “trattabili” e problemi “intrattabili” viene data in base al tipo di funzione che esprime il numero di passi necessario per i suoi algoritmi risolutivi. In particolare, se è noto un algoritmo risolutivo per il quale tale funzione di complessità è polinomiale, cioè il problema ammette un algoritmo polinomiale, allora il problema è detto trattabile (cioè, si dice che appartiene alla classe P). Se invece si è dimostrato che ogni possibile algoritmo risolutivo ha una funzione di complessità esponenziale, il problema è intrattabile (cioè, si dice che appartiene propriamente alla classe EXP). Mentre nel primo caso basta trovare un solo algoritmo polinomiale per definire il problema come trattabile, nel secondo caso la dimostrazione deve essere condotta prescindendo da specifici algoritmi, dal momento che l’insieme dei possibili algoritmi risolutivi è infinito e il fatto che un algoritmo di complessità polinomiale non sia stato finora trovato non implica che non esista.
Per discutere questa situazione da un altro punto di vista e far comprendere meglio che l’intrattabilità non può essere risolta con gli avanzamenti tecnologici, consideriamo cosa accadrebbe se avessimo un computer mille volte più veloce di quelli attuali. Avendo allora a disposizione 12 giorni, saremmo in grado di risolvere il secondo problema per un milione di città invece che per 100.000. Nel caso del terzo problema, nello stesso tempo di 12 giorni riusciremmo a passare solo da 50 a 60 città!
Il prossimo post, l’ultimo dedicato agli algoritmi, prenderà in considerazione una situazione di confine fra la trattabilità e l’intrattabilità molto rilevante sia da un punto di vista culturale che pratico.
( I post di questa serie sono basati sul libro dell’Autore La rivoluzione informatica: conoscenza, consapevolezza e potere nella società digitale, al quale si rimanda per approfondimenti. I lettori interessati al tema possono anche dialogare con l’Autore, su questo blog interdisciplinare )