di Giorgio Masiero*
*fisico e docente universitario

 Ogni 4 anni, al Congresso Internazionale dei Matematici, è assegnata la medaglia Fields ai giovani ricercatori qualificatisi per le scoperte più rilevanti. Il premio è soprattutto onorifico, a meno che la scoperta non rientri tra i “7 problemi del Millennio” del Clay Institute: allora ai 15.000 dollari canadesi della medaglia Fields si aggiunge il premio Clay di 1.000.000 di dollari USA. L’ultimo congresso si è svolto nel 2010 a Hyderabad ed ha assegnato solo medaglie Fields; nel precedente di Madrid invece, al russo Grigori Perelman era toccato anche il premio Clay per la dimostrazione della congettura di Poincaré, una questione che resisteva da un secolo agli assalti della ragione. La descrizione del problema e degli altri 6 ancora irrisolti si può trovare nel sito del Clay. A sorpresa Perelman non si mosse dalla sua San Pietroburgo per ritirare i premi, limitandosi a dire agli esterrefatti cronisti: “Ho risolto il problema, tanto mi basta”. Mostrava così la gioia perfetta di chi, col solo uso della mente, in anni di riflessioni dedicate a coniugare l’intuizione all’inferenza in vista d’un obiettivo, era riuscito a scalare difficoltà logiche inimmaginabili.

I moderni computer, implementati dei software adeguati, possono per la loro velocità di calcolo risolvere problemi complessi, che richiederebbero tempi astronomici al calcolo umano, ma hanno gravi limiti. Quali sono? Da che cosa traiamo indicazioni sui loro ambiti? L’unico giudice dei limiti dell’algoritmo e del processore è la ragione umana! Forse un giorno saranno dimostrati tutti i problemi del Clay; o forse no: per alcuni la dimostrazione potrebbe essere preclusa ad ogni tecnica. I due teoremi d’incompletezza di Gödel (1931) impattano proprio la capacità dell’algoritmo di dimostrare proposizioni matematiche e di costruire teorie scientifiche coerenti. Stando al primo teorema esistono in aritmetica, e quindi in tutta la matematica (di cui l’aritmetica costituisce il nucleo) e in tutte le scienze naturali (di cui la matematica è il linguaggio), enunciati veri che non si possono dimostrare per via algoritmica. Non è una questione di completezza degli assiomi, né di capacità di memoria, né di velocità elaborativa: semplicemente non esiste la procedura! Un esempio di questione matematica indecidibile fu trovato una cinquantina d’anni fa, con uno spettacolare teorema che procurò all’americano Paul Cohen la medaglia Fields nel 1966: è l’ipotesi del continuo di Cantor. Una delle prime domande su cui conto di avere risposta nell’altro mondo la riguarda: esistono infiniti intermedi tra i numeri naturali ed i reali?

La presenza di limiti all’algoritmo, tuttavia, ci è anche utile in questo mondo. Tornando alla lista Clay, leggiamo tra i 6 problemi irrisolti la sigla P vs NP. Essa sta ad indicare una questione cruciale in molti problemi d’ottimizzazione industriale, per es. nel process scheduling. Un problema è classificato tra quelli P (polinomiali) se è risolvibile in tempi ragionevoli da un calcolatore, magari dotato di velocità del processore e di capacità della RAM superiori a quelle odierne; rientra invece tra quelli NP (non polinomiali) se può essere risolto soltanto in modo bruto attraverso l’immissione ed il controllo di tutte le combinazioni e se richiede allo scopo un dispendio di risorse superiori all’età e all’energia dell’Universo. Non pensare, caro lettore, che i problemi NP riguardino chissà quali situazioni astratte: prova, se ci riesci, a calcolare il tragitto più corto per visitare in un unico giro 10 amici, abitanti in 10 località sparse della tua regione; o quello per la distribuzione giornaliera di un centinaio di pacchi di uno spedizioniere locale. Insomma un problema NP, anche se risolubile in teoria (da una “macchina di Turing”), non lo è in pratica: è oltre il limite fisico della tecnica…, a meno che con qualche scorciatoia matematica non sia traducibile in un problema di tipo P. La sfida posta dal Clay consiste proprio in ciò: i problemi NP sono sempre riducibili a problemi P?

Ricordate i numeri primi? Sono quelli divisibili solo per 1 e per se stessi: 2, 3, 5, 7, 11,… Anche se sembra ripetersi indefinitamente la stranezza di trovare ogni tanto due primi attaccati, detti “gemelli” (…, 107, 109, …, 599, 601, …, 821, 823, …), avanzando si diradano in media sempre più, ma sono infiniti (teorema di Euclide, III sec. a.C.): ciò significa che ne esistono di grandi quanto si vuole, anche da mille o un milione di cifre. La scomposizione poi è l’operazione che fattorizza un numero non primo (“composto”) nei suoi fattori primi, per es. 60 = 2 × 2 × 3 × 5. Se il numero composto non è troppo grande, la scomposizione è facile: se è pari si divide per 2, poi si prova per 3, poi per 5, ecc. Quando il numero è molto grande si ricorre ai calcolatori. Oggi, con sofisticati algoritmi che utilizzano recenti scoperte matematiche sulla distribuzione dei numeri primi (alcune, bellissime, hanno procurato nel 2006 una medaglia Fields all’australiano Terence Tao), un normale pc ci può dire in tempi ragionevoli se un dato numero di qualche centinaio di cifre è primo o no, e ci può anche trovare un nuovo primo di tali dimensioni. Non esiste tuttavia nessun software per nessun computer (sia pure il super-computer di Standard & Poor, o il K computer di Kobe da 8 milioni di miliardi di istruzioni al secondo, né quello 1.000 volte più veloce di cui si disporrà tra 10 anni) che sappia scomporre in tempi fisici il prodotto di due numeri primi di alcune centinaia di cifre.

Questa almeno è la situazione allo stato delle nostre conoscenze matematiche, dove la scomposizione resiste come problema NP. Sui tempi ultramondani della fattorizzazione di grossi numeri si fonda gran parte della crittografia per la sicurezza di internet (scambio dati riservati, transazioni bancarie, privacy, reti di trasporto, infrastrutture energetiche, comandi militari, ecc.). Così, quasi per una legge del contrappasso, quella finitudine dell’algoritmo che in apparenza ne denota negativamente i tratti applicativi, si trasforma nella capacità di dare sicurezza alle transazioni mondiali. Una tecnica onnipotente implicherebbe software capaci di fattorizzare tutti i numeri e di scardinare ogni crittografia; quindi sicurezza nulla ed impossibilità di transazioni riservate via internet; quindi, in definitiva, l’annullamento di ogni utilità del web, ridotto a veicolo di spam. Invece una tecnologia performante limitata consente una sicurezza che seppur finita resta performante: una sicurezza accettabile, pur se labile come ogni cosa di questo mondo, minacciata sempre da un hacker che trovi, forse domani, forse tra qualche anno, la via per districare il problema NP della scomposizione e tradurlo in uno di tipo P.

Morale. Giorni fa, prima di ritirare l’auto dal parcheggio a pagamento, sono passato alla cassa automatica e, trovatomi senza spiccioli, ho usato la mia carta di credito con chip e pin “ultrasicura, di ultima generazione” (secondo lo slogan della banca emittente): inseritala nello slot dedicato, ho digitato il pin sulla tastiera ed atteso la restituzione della carta. Tardando questa ad uscire, ho premuto il tasto “Annulla operazione” e l’ho estratta manualmente. Apparso comunque il messaggio di “Transazione eseguita”, me ne sono uscito tranquillamente dal parcheggio. A tarda serata però, un sms mi avvertiva che un acquisto di 1.659 € era appena stato eseguito in un negozio di confine con la mia card. Me l’avevano clonata! Realizzai allora che a rallentarne l’uscita dallo slot era stato uno skimmer fraudolentemente applicatovi per clonare il badge… e che la zingarella aggirantesi intorno alla cassa, apparentemente impegnata a richiedere un obolo ai passanti, era lì allo scopo di controllare il campo e di carpire dal moto delle dita il pin ai malcapitati. Le carte di credito usano sì teoremi che le rendono, allo stato delle nostre conoscenze matematiche, inattaccabili dai calcolatori, ma c’è una peculiarità della ragione umana che coniuga le più moderne tecnologie con le più ataviche doti d’intuizione e destrezza: quest’arte può battere sempre ogni impossibilità di cui è prigioniera la macchina. “Datemi una definizione d’intelligenza ed io vi dimostrerò che i calcolatori possono essere intelligenti”, preconizzava troppo ottimisticamente il britannico Alan Turing, del quale abbiamo festeggiato il 23 giugno scorso il centenario della nascita. Ebbene, non è l’intuizione una componente tra le più importanti, se non la prima, dell’intelligenza umana? e l’algoritmo non è alternativo all’intuizione, nella definizione fondante della computer science che tu, Alan, ne hai dato nel tuo memorabile scritto del 1936? Ricordi, lettore, il Dustin Hoffman di Rain man? Il personaggio mostra meglio di ogni disquisizione che l’autismo, anche quando fa prodigi nel calcolo, non coincide con l’intelligenza. A questa distinzione si deve se nessun adepto dell’Intelligenza Artificiale sa (anche vagamente solo immaginare come) scrivere un programma che dimostri per es. la proprietà commutativa della moltiplicazione, senza ricorrere al quinto assioma di Peano.

fonte UCCR