Spazio e Scienze

Problemino risolto con 200 terabyte di dati, volete provare?

Se la matematica del liceo vi ha spaventato meglio che passiate a un'altra notizia, perché in questa pagina parleremo di un problema matematico la cui soluzione occupa ben 200 terabyte. Oltre all'avvenimento vi spiegheremo nel modo più semplice possibile in cosa consisteva il problema, qual è la soluzione raggiunta grazie al contributo della Scuola Normale Superiore di Pisa e quali risorse sono state messe in campo grazie al ReCaS di Bari.

texas supercomputer 1024

Pensate che per occupare 1 terabyte di spazio ci vogliono 337.920 copie di Guerra e Pace, e che 200 TB sono più o meno lo spazio che occuperebbero tutti i testi digitalizzati conservati presso la US Library of Congress.

Per la cronaca la soluzione a questo problema batte tutti i record, compreso l'ultimo del 2014 che aveva occupato "solo" 13 gigabyte. I matematici che l'hanno trovata hanno avuto bisogno di 800 processori del supercomputer Stampede dell'università del Texas per elaborare tutte le possibilità e hanno dovuto creare una versione "compressa" della soluzione per le controverifiche, che occupa "solo" 68 gigabyte, perché per scaricare quella integrale ci vorrebbero 30mila ore (nelle fonti non è specificato a quale velocità di download).

Per capire la portata degli strumenti in campo abbiamo intervistato il professore Roberto Bellotti del ReCaS (Rete di Calcolo per SuperB e altre applicazioni) di Bari. "Da un punto di vista delle risorse computazionali e di memoria utilizzate, le quantità sono importanti ma non sicuramente 'ingestibili'. 800 core CPU e 200 terabyte sono quantità 'ragionevoli'. Il nostro Data Center ha circa 10.000 CPU e 6000 Terabyte di capacità di memorizzazione" spiega Bellotti.

"Naturalmente non è semplice far funzionare le risorse in parallelo in modo immediato (cosa che probabilmente hanno fatto questi ricercatori) quindi non mi permetterei di dire che il problema è, da un punto di vista dell'Information and Comunication Technologies, un problema banale.

Per la soluzione i matematici sono ricorsi, in parte, alla 'forza bruta' dei grandi calcolatori. Questo tipo di approccio permette, in modo indiretto, di sviluppare delle competenze trasversali sull'uso dei computer, in particolare viene privilegiato l'aspetto dell'ottimizzazione dei software, portando quindi la tecnologia informatica a fare calcoli e a scambiare dati tra computer diversi o tra computer e il mondo esterno, in modo più veloce ed efficiente.

Quindi le competenze acquisite per risolvere questi problemi sono 'spendibili' per i giovani ricercatori che se ne occupano, anche in ambiti diversi. Ad esempio la meteorologia, la finanza o le medicina personalizzata, che sono ambiti in cui la potenza di calcolo, la memorizzazione e la trasmissione dei dati sono di cruciale importanza per la risoluzione dei problemi".

Ma qual è questo problema di matematica così complesso da richiedere un supercomputer per venirne a capo? È conosciuto come il problema booleano delle terne pitagoriche e fu posto per la prima volta nel 1980 dal matematico californiano Ronald Graham. A risolverlo sono stati Marijn Heule dell'Università del Texas, Victor Marek dell'Università del Kentucky e Oliver Kullmann della Swansea University nel Regno Unito. Per spiegarvelo abbiamo chiesto l'aiuto di Giovanni Paolini, allievo del Corso di Perfezionamento, Classe di Scienze Matematica e Naturali, della Scuola Normale Superiore di Pisa.

solution 7824 copy

"Il problema era quello di colorare un determinato gruppo di numeri di due colori, rosso o blu. La colorazione doveva avere la seguente proprietà: ogni terna pitagorica (per esempio 3, 4,5) non può essere tutta dello stesso colore. Per esempio 3, 4 e 5 non possono essere tutti e tre rossi o tutti e tre blu".

Per rinfrescare le reminiscenze scolastiche, "una terna pitagorica è una terna di tre numeri naturali che possono essere i lati di un triangolo rettangolo – un triangolo che ha i cateti lunghi 3 e 4 e l'ipotenusa 5. Algebricamente sono le terne di numeri A, B, C che soddisfano il teorema di Pitagora, quindi A2+B2=C2".

"Il quesito era di colorare i numeri fino a un certo numero variabile, in modo che ogni terna pitagorica non fosse tutta dello stesso colore. Se fossero soltanto i numeri da 1 a 10 da colorare di rosso e di blu si riuscirebbe anche a mano una volta capito come funziona il problema. Fino a 100 e 1000 è più difficile ma qualcuno è riuscito.

La domanda è: 'fino a che numero si può fare?' Quindi non è solo una questione di 'tante combinazioni'; il problema è che a priori potrebbe essere che non ci sia un limite oltre il quale non si possa andare, non c'è nemmeno un numero finito di operazioni da fare".

Il computer invece ha scoperto che si può arrivare fino a 7.824. "Esatto, oltre non è più possibile. Il computer ha verificato che per 7.825 qualsiasi modo di colorare i numeri non soddisfa le richieste del problema". Quindi l'unico motivo per il quale è rimasto in sospeso questo problema da quando fu posto nel 1980 è la potenza di calcolo? "Sì e no. Sicuramente se fosse stato più facile da calcolare sarebbe stato risolto prima. Però ci sono problemi che sarebbero difficili da affrontare caso per caso ma che i matematici sono riusciti a risolvere con l'astuzia. A priori è possibile che ci sia una soluzione semplice che arriva a dare lo stesso risultato".

I matematici che hanno trovato la soluzione hanno sfruttato diverse tecniche e hanno lasciato al computer il compito di restringere il numero di combinazioni possibili da 102.300 triliardi (1023*10^23) a un solo trilione. Gli 800 processori hanno macinato dati per due giorni per sfoltire l'ultimo trilione di possibilità e alla fine hanno dato la soluzione.

La mole di dati prodotta per arrivare alla soluzione è stata tale per cui è stato necessario un software per verificare i risultati, e dimostrare che il risultato soddisfacesse i criteri della domanda iniziale posta da Graham.

I critici non mancano, per il fatto che nessun essere umano sia in grado di leggere la soluzione per intero e verificarla. Come sottolinea Evelyn Lamb di Nature "anche se il computer ha risolto il problema booleano delle terne pitagoriche, non ha fornito una ragione di fondo per il risultato, il che richiama un'obiezione filosofica comune a tutti i problemi risolti dai computer: i risultati possono essere corretti, ma è davvero matematica?". Se la matematica è una forma di progresso della conoscenza umana e la comprensione del significato dei numeri spiega l'universo e tutto quello che ci circonda, soluzioni sfornate dai computer e che l'uomo non capirà mai sembrano andare contro i principi della disciplina.

Paolini spiega che "la questione è delicata e anche un po' filosofica. Abbiamo ottenuto una dimostrazione molto lunga che di fatto può essere letta solo da un computer e non da un essere umano. Ciò nonostante questa è una dimostrazione. Il punto è che giudicare che cos'è una dimostrazione non dovrebbe dipendere dalla nostra capacità di esseri umani di verificarla. Quello che dice Lamb poi è un discorso diverso ed è un'opinione condivisibile".

Con quale frequenza usate i computer per trovare delle soluzioni?

"Dipende moltissimo dalla disciplina. A me è capitato di usare il computer non per fare dimostrazioni, ma per capire meglio come funzionano le cose per poi fare io una dimostrazione. Faccio calcolare a un computer un certo numero di casi, mi faccio dare la risposta e capisco quale potrebbe essere la soluzione generale, e magari basandomi sui calcoli che ha fatto il computer trovo la risposta per tutti i casi. Una cosa è usare il computer in questo modo, tutt'altra le dimostrazioni automatiche, che è questo caso.  Dimostrazioni prodotte da computer sono molto rare almeno nella mia area (topologia algebrica)".