Recentemente il matematico e informatico americano di origine ungherese László “Laci” Babai ha annunciato di aver trovato un algoritmo quasipolinomiale per il problema dell’isomorfismo di grafi. Capiamo di cosa si tratta e quali conseguenze può avere questa scoperta.

di Vincenzo Bonifaci

Pochi giorni fa László Babai, matematico e informatico dell’università di Chicago, ha annunciato di aver risolto un problema della teoria della complessità computazionale noto come problema dell’isomorfismo di grafi. Babai è noto come esperto internazionale di complessità computazionale, area di ricerca in cui ha vinto anche il prestigioso Premio Gödel nel 1993.

La teoria della complessità computazionale, disciplina nata negli anni 1970 e che da allora si è estesa rapidamente dall’informatica ad altri settori, studia la difficoltà intrinseca dei problemi matematici dal punto di vista della loro soluzione automatica al calcolatore. Alcuni problemi – ad esempio: dati due interi, determinarne il massimo comun divisore – ammettono algoritmi risolutivi efficienti, il cui numero di passi cresce in maniera “graduale” al crescere della dimensione dei dati di input del problema; tali problemi sono chiamati polinomiali, o semplicemente P. Altri problemi – ad esempio, determinare se un insieme di interi dato contenga un sottoinsieme avente una certa somma – sono classificati come NP-ardui, e non solo non si conoscono algoritmi efficienti che li risolvano, ma, al contrario, molti addetti ai lavori congetturano che ogni algoritmo per un problema NP-arduo richieda talvolta un numero di passi esponenziale nella dimensione dei dati del problema; in altre parole, il tempo di risoluzione di un problema NP-arduo dovrebbe necessariamente “esplodere” al crescere della dimensione dei dati del problema. L’ipotesi che nessun problema NP-arduo possa al tempo stesso essere polinomiale è ad oggi irrisolta, ed è nota come P contro NP; si tratta di unadelle sette grandi sfide matematiche per la soluzione delle quali il Clay Mathematics Institute ha messo in palio un milione di dollari.

Nella stragrande maggioranza dei casi, i problemi computazionali di interesse applicativo sonostati già classificatinei decenni passati come polinomiali o come NP-ardui. Alcuni hanno richiesto sforzi maggiori di altri: l’importante problema dell’ottimizzazione lineare, ad esempio, già studiato a partire dal dopoguerra, è stato dimostrato essere polinomiale nel 1979 da Leonid Khachiyan. Un altro importante esempio è il problema di decidere se un intero dato rappresenti un numero primo o no; questo problema, le cui radici affondano nell’antichità della storia della matematica, è stato dimostrato essere polinomiale soltanto nel 2002 da Manindra Agrawal, Neeraj Kayal, e Nitin Saxena.

I pochissimi problemi sfuggiti a questa classificazione sono rimasti in una sorta di limbo computazionale: tra questi, per l’appunto, il problema dell’isomorfismo di grafi. Di cosa tratta quest’ultimo? Un “grafo” altro non è che l’incarnazione matematica di una rete, formata da “nodi” e da connessioni tra nodi. Nel problema dell’isomorfismo di grafi sono date due reti, e si chiede di determinare se esse abbiano la stessa struttura: ovvero, se sia possibile mettere in corrispondenza i nodi dell’una con i nodi dell’altra in maniera tale che le connessioni siano in corrispondenza biunivoca (vedi Figura 2).

Figura 2: Nonostante la loro diversa apparenza, queste due reti hanno la stessa struttura. Ogni nodo di una delle reti corrisponde ad un nodo dell’altra ed è connesso nello stesso modo agli altri nodi. Nodi corrispondenti hanno lo stesso colore. (Immagine tratta da Wikimedia Commons)

L’applicazione principale del problema dell’isomorfismo di grafi è nel confronto e identificazione di composti chimici; in questo caso, i nodi rappresentano gli atomi del composto e le connessioni ne rappresentano i legami chimici. Avere un metodo efficiente di confronto permette di cercare rapidamente un composto in un database chimico. Il problema ha comunque ulteriori applicazioni in campi disparati, dall’analisi delle reti sociali al confronto di impronte digitali.

Un algoritmo banale per il problema dell’isomorfismo di grafi consiste nel provare tutte le N! permutazioni degli N nodi del grafo di partenza, verificando per ciascuna permutazione se essa genera una corrispondenza biunivoca con il grafo di arrivo. Si tratta però di un metodo estremamente lento, con un numero di passi che cresce in maniera più che esponenziale al crescere di N.

Sebbene varie ottimizzazioni possano certamente essere apportate all’algoritmo che enumera tutte le permutazioni, i ricercatori fino ad oggi non erano riusciti a migliorare di molto la situazione. Il più efficiente algoritmo pubblicato rimane quello del 1983 di Eugene Luks; la complessità dell’algoritmo di Luks però, per alcune reti è poco meno che esponenziale, e quindi proibitiva. L’algoritmo proposto da Babai, se confermato, avrebbe invece una complessità “quasipolinomiale”, ovvero poco più che polinomiale. Si tratterebbe quindi di un miglioramento sostanziale da un punto di vista teorico, che di fatto accomunerebbe lo sfuggente problema dell’isomorfismo di grafi alla classe dei problemi polinomiali.

Dal punto di vista pratico, per la verità, esistono già approcci abbastanza efficienti per risolvere il problema dell’isomorfismo per le reti che più spesso si presentano nelle applicazioni, per quanto tali algoritmi possono risultare inefficienti se applicati ad alcuni tipologie “sfortunate” di reti. Dal punto di vista pratico, insomma, non cambierebbe molto. La conseguenza più importante del risultato di Babai sarebbe piuttosto quella di contribuire a semplificare il panorama offerto dalla teoria della complessità computazionale, in quanto uno dei pochissimi esempi noti di problemi non classificabili né come polinomiali, né come NP-ardui, verrebbe meno. Questo potrebbe a sua volta contribuire a chiarire almeno in parte la questione da un milione di dollari “P contro NP”. Per questo motivo gli esperti attendono con grande curiosità di conoscere i dettagli della dimostrazione di Babai e le tecniche matematiche da lui utilizzate.

Dopo il problema dell’isomorfismo di grafi, uno degli ultimi esempi di problema computazionale non ancora classificato rimarrebbe il problema di fattorizzare numeri interi. A differenza dell’isomorfismo di grafo, non sono noti algoritmi efficienti, né in teoria né in pratica, per fattorizzare interi a molte cifre, e lo sviluppo di un algoritmo efficiente per tale problema potrebbe avere delle conseguenze imprevedibili: la sicurezza delle transazioni finanziarie usate ogni giorno sul Web è in gran parte basata, infatti, proprio sulla (presunta) difficoltà di fattorizzare grandi numeri. Forse, in questo caso, chi scoprisse un algoritmo efficiente per la fattorizzazione preferirà però tenere per sé i dettagli della scoperta.

Roberto Natalini

Roberto Natalini [coordinatore del sito] Matematico applicato. Dirigo l’Istituto per le Applicazioni del Calcolo del Cnr e faccio comunicazione con MaddMaths!, Archimede e Comics&Science.