Fra gioco e applicazione /2: un problema da un milione di dollari

Dopo la teoria e le applicazioni nate da un problema da osteria, oggi parlo di un’altra parte della teoria dei grafi (vedi l’appendice del post correlato), nata da un gioco commerciale e sfociata in un problema su cui è stata posta una “taglia” di un milione di dollari.

Sir William Rowan Hamilton era un grande matematico irlandese. Rivoluzionò la meccanica razionale e inventò i quaternioni e molto altro. Quando nel 1859 un amico gli propose di inventare un gioco da tavolo, Hamilton gliene presentò uno che aveva ideato due anni prima. Non so se si fosse ispirato al problema risolto da Eulero: dato un grafo, è possibile percorrere tutti i suoi spigoli esattamente una volta e tornare al punto di partenza?

È frequente, in teoria dei grafi, osservare un fenomeno interessante che riguarda gli spigoli e riformularlo in termini di vertici o viceversa. Forse è così che Hamilton ideò l’Icosian game (vedi figura): in un grafo, in cui i vertici rappresentavano città, si trattava di trovare un percorso chiuso che toccasse tutti i vertici una volta sola. Il gioco venne costruito, ma fu un fiasco commerciale; Hamilton ne ricavò 25 sterline.

Fiasco o no, i matematici vennero stuzzicati dal problema generale: quali sono i grafi (chiamati hamiltoniani) in cui esiste un ciclo hamiltoniano, cioè un percorso chiuso che passa esattamente una volta per ogni vertice? Ora, l’analogo problema per i grafi euleriani era stato risolto da Eulero stesso: c’è un tour di Eulero se e solo se a ogni vertice afferisce un numero pari di spigoli. Sorprendentemente, una buona caratterizzazione analoga per i grafi hamiltoniani non è ancora stata trovata!

Legato al problema di Eulero c’è un problema di ottimizzazione, di cui ho parlato nel post precedente: un postino deve percorrere tutte le strade del suo quartiere ma, nel caso sia costretto a ripercorrerne qualcuna, vuole minimizzare il suo percorso.

Esistono algoritmi (cioè procedimenti di calcolo) che risolvono il problema. C’è tutta un’area di ricerca a cavallo fra matematica e informatica, quella della complessità computazionale, volta a valutare quanto è buono un algoritmo.

Il problema, che dev’essere risolto dall’algoritmo in questione, ha una sua grandezza “n”; per esempio, nel nostro caso, n è il numero di strade da percorrere. La complessità dell’algoritmo è, a grandi linee, il numero di calcoli necessari, in funzione di n. I migliori algoritmi conosciuti per il problema del postino sono di complessità polinomiale, cioè la funzione di n è un polinomio. Questo è buono! Lo spauracchio dei programmatori, invece, è quando la complessità è esponenziale.

Legato al problema di Hamilton c’è un altro problema di ottimizzazione, quello del commesso viaggiatore: un agente di commercio deve visitare tutte le città della sua zona (e tornare a casa); deve dunque progettare, se possibile, un ciclo hamiltoniano e comunque deve minimizzare la lunghezza totale del suo percorso. Bene, contrariamente al caso del postino, per questo problema tutti gli algoritmi conosciuti sono di complessità esponenziale!

Il problema non è importante solo per commessi viaggiatori: è il paradigma di innumerevoli situazioni in cui, per esempio, si deve progettare una successione di azioni da compiere o si devono allocare risorse. Come esempi concreti: la successioni di operazioni di una macchina che può esercitare diverse funzioni; lo stazionamento di equipaggi di aeroplani; i test di circuiti elettronici, eccetera.

Quello del commesso viaggiatore è il problema tipo di una intera classe di problemi chiamati NP-completi, tutti equivalenti fra loro. Sono problemi che, per adesso, sono risolti solo da algoritmi di complessità esponenziale. Se si trovasse un algoritmo di complessità polinomiale per uno di loro, questo si rifletterebbe sulla soluzione di tutti.

Questa faccenda è di tale importanza che è uno dei sette problemi del millennio: il Clay Institute bandì per ognuno di essi un premio di un milione di dollari! Se qualcuno inventasse un algoritmo di complessità polinomiale per risolvere il problema del commesso viaggiatore (ma anche quello della ricerca di un ciclo hamiltoniano) intascherebbe una bella somma.

Ma non avremmo tanto da stare allegri: tutti i metodi di crittografia a chiave pubblica, cioè quelli che garantiscono la sicurezza delle nostre transazioni con le banche, con Amazon, con eBay eccetera (riconoscibili dall’indirizzo web che comincia con https) sono basati su problemi NP (ad essi correlati) e diventerebbero immediatamente delle ciofeche.