Come programmatore sono sempre stato affascinato dagli algoritmi, specialmente se compatti ed eleganti

Ci sono, però, dei problemi per la cui soluzione non esistono algoritmi efficienti; di contro, per gli stessi problemi, se viene presentata una soluzione, questa è immediatamente e facilmente verificabile come corretta. Prendete, per esempio, una mappa con un sacco di isole e ponti: non esiste un algoritmo efficiente che tracci un percorso per visitare tutte le isole una sola volta, ma se vi viene presentata una soluzione, è facile capire se sia corretta. Un altro problema da un lato più teorico, ma con tremende ripercussioni pratiche è, dato un numero, capire se sia il prodotto di due numeri primi e di quali. Se quest’ultimo problema è semplice con numeri piccoli, non lo è, fortunatamente, per numeri molto grossi. Perché «fortunatamente»? Perché la gran parte di transazioni informatiche crittografate si basa su questo assunto. Se leggete che qualcuno ha trovato un algoritmo per fattorizzare rapidamente numeri di grandi dimensioni, iniziate a preoccuparvi davvero.

Charles Stross, uno dei miei autori di fantascienza preferiti, ha addirittura ipotizzato che la soluzione per via algoritmica di problemi NP-completi porterebbe rapidamente alla creazione di una singolarità tecnologica con conseguente fine della nostra civiltà. Robot 52 ha pubblicato il gustosissimo raccorto Anticorpi ambientato nell’universo della Lavanderia in cui Stross analizza, appunto, questa eventualità.

Per ora non è nemmeno stato dimostrato se esistano soluzioni algoritmiche ai problemi NP-completi. Secondo un articolo di Scott Aaronson pubblicato sull’ultimo numero di Le Scienze (a cui vi rimando per una trattazione più autorevole di questa), anche con i computer quantici non sarebbe possibile risolvere ogni tipo di problema, in particolar modo quelli NP-completi, per un mero fatto di leggi fisiche.

Meglio: di leggi fisiche attuali, perché sarebbe possibile realizzare un computer in grado di risolvere ogni tipo di problema (anche quelli ancora più complessi dei problemi NP-completi) usando leggi della fisica in contrasto con quelle attuali. Mi ha divertito abbastanza il concetto di computer che si basa sulle curve temporali chiuse (il nome scientifico dei viaggi arbitrari nel tempo): si tratta in pratica di un computer che risolve un problema in un tempo lungo a piacere che comunichi, però, la soluzione appena dopo che gli è stata sottoposta.

Forse un computer del genere non verrà mai realizzato, ma se lo fosse mi eviterebbe, finalmente, di sentire lamentele sulla lentezza di Windows. Il vantaggio sarebbe anche che la fine dell’Universo verrebbe prorogata indefinitivamente a causa del tempo necessario per far girare Windows.