La ricerca del Santo Graal dell’informatica, vale a dire la soluzione del problema P vs NP, potrebbe permettere di affrontare le domande ancora in sospeso sul futuro dell’informatica e della matematica teorica.
di Siobhan Roberts
1. La stimata rivista “ACM Transactions on Computational Theory”, che tratta di “eccezionali ricerche originali che esplorano i limiti del calcolo fattibile”, aveva già anticipato la ricerca. Il risultato pretendeva di risolvere il “P versus NP”, il problema per eccellenza dell’informatica teorica, sulla cui soluzione pendeva un premio di un milione di dollari.
Questo problema coinvolge domande centrali nel campo matematico: Perché alcuni problemi sono più complessi di altri? Quali problemi possono realisticamente risolvere i computer? Quanto tempo ci vorrà?
Anche i riscontri in ambito filosofico e in campo pratico sono di grande portata. “Si tratta di una delle domande più profonde che gli esseri umani abbiano mai posto”, dice Scott Aaronson, un informatico dell’Università del Texas, ad Austin, autore di Quantum Computing Since Democritus. “A molti”, aggiunge ”piace descriverlo come ‘probabilmente il problema centrale irrisolto dell’informatica teorica’”.
Un modo per capire di cosa si sta parlandop è il seguente: “P” rappresenta i problemi che un computer può risolvere facilmente. “NP” indica problemi che, una volta risolti, sono facili da tenere sotto controllo, come i puzzle o il Sudoku e corrispondono a quelli più ostinati e urgenti che la società deve affrontare.
La domanda da un milione di dollari posta da P contro NP è questa: queste due classi di problemi sono la stessa cosa? Vale a dire, i problemi che sembrano così difficili potrebbero in realtà essere risolti con un algoritmo in un ragionevole lasso di tempo, se solo si potesse trovare l’algoritmo giusto e diabolicamente veloce? Se è così, allora le soluzioni algoritmiche potrebbero portare a cambiamenti sociali di proporzioni utopiche in medicina, ingegneria ed economia, biologia ed ecologia, neuroscienze e scienze sociali, industria, arte e persino politica.
A volte le classificazioni si evolvono: i problemi difficili si rivelano facili quando i ricercatori trovano soluzioni più efficienti. Il test se un numero è primo, per esempio, è noto per essere nella classe NP dalla metà degli anni 1970. Ma nel 2002, tre scienziati informatici dell’Indian Institute of Technology Kanpur hanno ideato una prova incontrovertibile e un algoritmo intelligente che alla fine ha confermato che il problema era anche in P.
Se tutti i problemi difficili potessero essere trasformati con un simile gioco di prestigio algoritmico, le conseguenze per la società, per l’umanità e per il nostro pianeta, sarebbero enormi.
Per cominciare, i sistemi di crittografia, la maggior parte dei quali basati su problemi NP, verrebbero violati. Avremmo bisogno di trovare un approccio completamente diverso all’invio di comunicazioni sicure. Il ripiegamento delle proteine, una grande sfida in biologia di 50 anni fa, diventerebbe più gestibile, sbloccando nuove capacità per progettare farmaci e scoprire enzimi che abbattono i rifiuti industriali.
Da 50 anni, i ricercatori impegnati nei settori a cavallo della logica matematica e della tecnologia di calcolo elettronico, hanno affrontato questa sfida. Per Manuel Sabin, un informatico che ha appena terminato un dottorato di ricerca all’Università di Berkeley, la ricerca potrebbe essere donchisciottesca, ma vale la pena di portarla avanti.
Timothy Gowers, un matematico dell’Università di Cambridge, definisce questi tentativi “una delle mie malattie matematiche personali”. Stephen Cook, un informatico dell’Università di Toronto, inquadrò il problema e definì il campo della complessità computazionale con un documento seminale nel 1971. Per questo lavoro, vinse il Turing Award, l’equivalente informatico del Premio Nobel. Ma non ha avuto fortuna a trovare una soluzione.
2. Michael Sipser, un informatico del MIT, dice di aver trascorso un decennio a indagare sul problema. I suoi studi sono cominciati negli anni 1970 con una scommessa (persa) con il suo compagno di studi Len Adleman, che la soluzione sarebbe arrivata entro la fine del secolo.
Negli anni 1980, ottenne un buon risultato risolvendo una versione del problema con un modello computazionale “ristretto”, portando a una serie di risultati promettenti. Oggi, Sipser torna ancora sul problema di tanto in tanto e tiene innumerevoli conferenze sull’argomento.
L’informatico del MIT spiega il problema di P contro NP partendo da una moltiplicazione di base: 7 × 13 = ?. La risposta, 91, è abbastanza facile da calcolare a mente. Per i numeri più grandi, i computer impiegano pochissimo tempo. Si provi, per esempio, a trovare i due numeri primi di 97 cifre che si moltiplicano per produrre questo numero molto grande:
310 7418240490 0437213507 5003588856 7930037346 0228427275 4572016194 8823206440 5180815045 5634682967 1723286782 4379162728 3803341547 1073108501 9195485290 0733772482 2783525742 3864540146 9173660247 7652346609
Questo problema di fattorizzazione faceva parte di una sfida per valutare la difficoltà di decifrare le chiavi RSA utilizzate nella crittografia. Per risolvere il problema ci sono voluti 80 processori e cinque mesi di elaborazione continua, spiega Sipser, il che equivale a circa 33 anni con un solo processore. Il factoring è un problema difficile perché tutti i metodi attuali cercano la risposta tramite la “forza bruta”, controllando il numero astronomico di possibilità una per una. Anche per un computer, questo è un processo lento.
“La domanda interessante per Sipser è capire se esiste un modo per risolvere il problema del factoring che sviluppi rapidamente la risposta senza tutta la fase di ricerca. Non si sa. Domande come questa arrivano al cuore della complessità computazionale. Aaronson ha assemblato un “Complexity Zoo”, un catalogo online con 545 classi di problemi in costante aumento. Ciascuno è classificato in base alla sua complessità, o difficoltà, e alle risorse (tempo, memoria, energia) necessarie per trovare soluzioni.
Come avrebbe voluto la serendipità scientifica, un matematico sovietico, Leonid Levin, è arrivato a un risultato equivalente a quello di Cook più o meno nello stesso momento. P è la classe di problemi che possono essere risolti da un computer in un ragionevole lasso di tempo. Più specificamente, i problemi P sono quelli per i quali il tempo necessario per trovare una soluzione può essere descritto da una funzione polinomiale, come n^2. Negli algoritmi polinomiali, n è la dimensione dell’input e la crescita rispetto a questo input avviene a un ritmo ragionevole (in questo caso, alla potenza di due).
Al contrario, alcuni problemi NP più complessi potrebbero essere risolvibili solo da algoritmi con tempi di esecuzione definiti da una funzione esponenziale, come 2^n, producendo un tasso di crescita esponenziale (come avviene con la diffusione del covid). NP, come lo descrive Aaronson, è “la classe delle speranze deluse”. Tuttavia, non tutti i problemi di NP sono difficili. La classe NP infatti contiene la classe P, perché i problemi con soluzioni facili sono, ovviamente, anche semplici da controllare.
I problemi più impegnativi di NP hanno spesso importanti applicazioni pratiche, ma una ricerca esaustiva di una soluzione con la forza bruta probabilmente andrebbe avanti per un tempo troppo lungo prima di produrre una risposta. Se un algoritmo di ricerca a forza bruta è il miglior algoritmo possibile, allora P non è uguale a NP.
Tra gli esperti, il consenso è intorno a questa formula: P ≠ NP. La maggior parte lascia solo un piccolo spiraglio aperto alla possibilità del contrario. “Darei una probabilità dal 2 al 3 per cento che P sia uguale a NP”, dice Aaronson.
Il risultato della ricerca pubblicato a luglio ha presentato esattamente una prova di questa possibilità. Ma era solo l’ennesima riprova di una lunga tradizione di soluzioni che non passano l’esame. Entro un giorno dalla pubblicazione, in un susseguirsi di eventi degni di Monty Python, il documento è stato rimosso dal giornale online per poi riapparire brevemente prima di scomparire definitivamente.
Si trattava della versione più recente di un articolo che l’autore aveva pubblicato più di 60 volte sul server di prestampa arXiv nell’ultimo decennio. Il caporedattore della rivista ha spiegato su Twitter che il risultato era stato rifiutato, ma a causa di un errore umano, l’indicazione del giornale era in qualche modo passata da “rifiuta” ad “accetta”.
3. All’inizio di agosto, quando ho incontrato Steve Cook nel suo ufficio nel campus, non aveva né visto né sentito parlare di questo pasticcio. L’informatico, ora 81enne, si è ritirato solo di recente, lasciando spazio a suo figlio James. Steve stava sgombrando il suo ufficio. Al centro della stanza c’era un gigantesco bidone della raccolta differenziata, pieno di vecchi numeri ingialliti del “Journal of Symbolic Logic” e una pila di elenchi telefonici di Toronto.
Nel corso degli anni, Cook ha visto molte presunte soluzioni al problema P vs. NP. Nel 2000, dopo che il Clay Mathematics Institute lo inserì tra i sette “Problemi del millennio” irrisolti (ognuno del valore di un premio di 1 milione di dollari ), fu inondato di messaggi da persone che pensavano di avere trovato la risposta giusta. Non era così. Circa la metà affermava di aver dimostrato che P è uguale a NP; l’altra metà sosteneva il contrario. C’è anche chi riteneva di aver dimostrato la verità di entrambe le formule.
Cook, nel suo articolo del 1971, ipotizzò che P non fosse uguale a NP. Da allora ha investito una quantità significativa del suo tempo per dimostrarlo. Nella sua onestà intellettuale confessava: “Onestamente, ho fatto pochi progressi …”. Questa carenza non ha impedito, nel 2019, di organizzare al Fields Institute for Research in Mathematical Sciences dell’Università di Toronto un simposio in onore di Cook per il 50° anniversario del problema principe della complessità computazionale. Christos Papadimitriou, un informatico della Columbia University che ha trascorso gran parte della sua carriera lavorando a P vs. NP, ha aperto l’evento con un intervento retrospettivo.
Dopo una lunga dissertazione sulle ricerche secolari di soluzioni, Papadimitriou è arrivato ad Alan Turing, il matematico britannico il cui articolo del 1936 On Computable Numbers formalizzava le nozioni di “algoritmo” e “calcolo”. Turing dimostrò anche – con la sua idea di “macchina di calcolo universale” – che non esiste un modo “meccanico” (cioè eseguito da una macchina) per dimostrare la verità o la falsità delle affermazioni matematiche, per distinguere il dimostrabile dall’indimostrabile.
A parere di Papadimitriou, l’articolo di Turing costituiva il certificato di nascita dell’informatica e comprovava che il settore di ricerca è nato con una profonda comprensione dei propri limiti, al contrario di altre scienze che arrivano a questa consapevolezza in una fase avanzata.
Non molto tempo dopo che le idee di Turing (e di altri) hanno trovato incarnazione nei primi computer, gli scienziati si sono interrogati sulle capacità e sui limiti intrinseci delle macchine. All’inizio degli anni 1950, John von Neumann, il pioniere ungaro-americano del computer moderno, “parlava di algoritmi polinomiali rispetto a quelli esponenziali”, ha ricordato Papadimitriou. Era l’alba della nuova teoria della complessità computazionale.
Il punto cruciale era che solo gli algoritmi polinomiali sono in qualche modo buoni o pratici o degni di essere mirati a un problema, mentre un algoritmo esponenziale, ha spiegato Papadimitriou, “è l’equivalente algoritmico della morte”.
Cook iniziò a pensare alla complessità a metà degli anni 1960. Mentre lavorava al suo dottorato di ricerca ad Harvard, aveva riflettuto sulla possibilità di dimostrare, dati alcuni modelli computazionali, che la moltiplicazione è più complessa dell’addizione (ancora oggi un problema aperto).
Nel 1967, come sostenuto in un libro su Cook pubblicato dall’Association for Computing Machinery (ACM), mentre era postdoc a Berkeley, aveva già elaborato una formulazione delle classi di complessità che divennero note come P e NP, e si era posto la domanda se P fosse uguale a NP. (Più o meno nello stesso periodo, altri, incluso lo scienziato informatico Jack Edmonds, dell’Università di Waterloo, portavano avanti tesi simili).
Ma il campo dell’informatica era solo all’inizio, e per la maggior parte degli scienziati e dei matematici tali idee erano poco familiari, se non addirittura strane. Dopo quattro anni al dipartimento di matematica di Berkeley, Cook fu preso in considerazione per il ruolo, ma non gli venne offerto un posto, probabilmente per l’opposizione di alcuni illustri matematici.
Nel 1970, Cook si trasferì all’Università di Toronto. L’anno successivo fu quello della svolta. Presentato a un simposio dell’ACM tenutosi a maggio a Shaker Heights, Ohio, il documento affinava il concetto di complessità e definiva un modo per caratterizzare i problemi più difficili in NP.
Dimostrava, inoltre, che il problema di soddisfacibilità, vale a dire cercare una soluzione per una formula data con un insieme di vincoli, era quello centrale in NP e che tutti gli altri potevano esservi ricondotti. Il suo era un teorema cruciale: se esiste un algoritmo in tempo polinomiale che risolve il problema di soddisfacibilità, allora quell’algoritmo servirà da passe-partout, sbloccando soluzioni a tutti i problemi in NP. E se esiste una soluzione in tempo polinomiale per tutti i problemi in NP, allora P = NP.
Tra gli scienziati informatici, il teorema di Cook è iconico. Leslie Valiant, di Harvard, ha ricordato al simposio del 2019 esattamente dove e quando ne ha sentito parlare per la prima volta. Dopo aver terminato gli studi universitari in matematica, aveva iniziato un dottorato di ricerca in informatica. Un giorno, Valiant si imbatté nel teorema di Cook. “In un istante, l’informatica per me era diventata qualcosa di concreto”.
Poi, nel 1972, Dick Karp, un informatico a Berkeley, dopo la lettura dell’articolo esoterico di Cook, dimostrò che molti dei classici problemi computazionali di cui aveva esperienza, essenzialmente tutti i problemi che non sapeva come risolvere, inerenti la programmazione matematica, la ricerca operativa, la teoria dei grafi, la combinatoria e la logica computazionale possedevano la stessa proprietà trasformazionale che Cook aveva trovato con il problema della soddisfacibilità.
In totale, Karp trovò 21 problemi, tra cui quello dello zaino, vale a dire cercare il modo ottimale per sistemare in uno spazio ristretto gli oggetti essenziali, quello del commesso viaggiatore, ossia trovare il tragitto più breve possibile di andata e ritorno da un luogo, e quello dell’albero di Steiner, che consiste nel collegare una serie di punti dati mediante i percorsi rettilinei o curvilinei più brevi.
Karp mostrò che i problemi di questa speciale raccolta erano tutti equivalenti, il che a sua volta fece capire che il modello identificato da Cook non era un fenomeno isolato, ma un sistema di classificazione di sorprendente potenza e portata. La soluzione di uno li avrebbe risolti tutti.
Papadimitriou considera l’NP-completo come uno strumento versatile che fa risparmiare tanto tempo, rinunciando alla soluzione esatta, ma passando alla risoluzione di un’approssimazione o di una variazione del problema.
A suo parere, il fenomeno della completezza NP e la ricerca P vs. NP sono il destino dell’informatica. Anche un matematico sovietico, Leonid Levin, convenne su un risultato equivalente a quello di Cook più o meno nello stesso momento. Levin, ora alla Boston University, svolse la sua attività dietro la cortina di ferro. Quando emigrò in America nel 1978, il risultato del suo lavoro divenne noto come teorema di Cook-Levin.
Una decina di anni dopo, negli archivi di Princeton del logico austriaco Kurt Gödel fu scoperta una “lettera perduta”. Nel 1956 aveva scritto a von Neumann chiedendo se un problema logico, che nel linguaggio moderno sarebbe chiamato NP-completo, potesse essere risolto in tempo polinomiale. Se fosse così, affermò, “avrebbe conseguenze di enorme impatto”.
4. Mentre mezzo secolo di lavoro non ha prodotto nulla di vicino a una soluzione, alcuni risultati colpiscono l’immaginazione: un articolo del 2004 sviluppò una prova per P = NP usando bolle di sapone come meccanismo di calcolo analogico.
Negli anni 1970 il teorema di Roan Fagin, di IBM, caratterizzò la classe NP in termini di logica matematica. Risolse il problema più di una volta, ma i risultati non durarono mai più di qualche giorno prima che venisse scoperto un bug. Fagin ha recentemente ottenuto finanziamenti per un progetto P vs. NP dal programma Exploratory Challenges di IBM a sostegno della ricerca più audace.
Ma la maggior parte dei teorici della complessità sogna più in piccolo, optando invece per approcci indiretti che permettano di rimodellare o riformulare il problema, di esplorarne i dintorni correlati. Ryan Williams, un informatico del MIT, sta cercando di inquadrare il problema dall’alto e dal basso, studiando la natura dei “limiti superiori” e dei “limiti inferiori”.
Un limite superiore, in termini semplici, è una specifica affermazione matematica che esiste un algoritmo concreto che risolve un particolare problema senza superare l’impiego di una certa quantità di risorse (tempo, memoria, energia). Un limite inferiore è l’opposto intangibile: è un’affermazione generale di impossibilità, che mostra che tale algoritmo non esiste universalmente. Uno degli obiettivi della ricerca di Williams è rendere i limiti inferiori costruttivi e concreti, oggetti matematici con caratteristiche descrivibili. A suo parere, approcci più costruttivi ai limiti inferiori sono “ciò che ci manca nella attuale teoria della complessità”.
Williams ha fissato la probabilità che P ≠ NP a un 80 per cento. Ma ultimamente alcuni ricercatori del settore esprimono dubbi anche su questo livello di certezza. “Sempre di più, sto iniziando a chiedermi se P sia uguale a NP”, afferma Tonian Pitassi, informatico all’Università di Toronto ed ex studente di dottorato di Cook. Il suo approccio per aggirare il problema è quello di studiare modelli analoghi su scale più grandi e più piccole.
“A volte generalizzare la domanda aiuta a chiarire”, dice. Ma nel complesso, non è stato così. “La maggior parte delle persone pensa che P non sia uguale a NP”. Storicamente, sottolinea Pitassi, a volte sono emersi risultati sorprendenti dal nulla, impossibilità apparentemente dimostrate possibili dai progettisti di algoritmi intelligenti. Lo stesso potrebbe accadere con P contro NP, forse tra altri 50 anni o un secolo.
Uno dei risultati più importanti in tutta la teoria della complessità, per esempio, è stato ottenuto da David Barrington, dell’Università del Massachusetts, ad Amherst, nel 1989. Il matematico e fisico ideò un algoritmo intelligente, che invece di richiedere una quantità illimitata di memoria, utilizzava solo cinque bit di informazioni, sufficienti per specificare un numero compreso tra uno e 32 (incluso) o una parola di due lettere.
Un risultato più recente e correlato, del 2014, colse di sorpresa James Cook. Attingendo al teorema di Barrington, sfruttò la memoria in un modo meravigliosamente strano. Come suggerito nel titolo dell’articolo, da Harry Buhrman e collaboratori dell’Università di Amsterdam, si tratta di “informatica con una memoria piena”. James può snocciolare il paragrafo introduttivo del documento praticamente alla lettera:
Si immagini il seguente scenario. Si desidera eseguire un calcolo che richiede più memoria di quella attualmente disponibile sul computer. Un modo per affrontare questo problema è installare un nuovo disco rigido. Ma il disco rigido è pieno di dati e non li si vuole cancellare. Si può utilizzare l’hard disk per i fare i calcoli, alterandone potenzialmente il contenuto, garantendo che al termine del calcolo l’hard disk torni allo stato originale con tutti i dati intatti?
La risposta, a differenza di quanto viene spontaneo pensare, è sì.
James parla di “memoria presa in prestito”. A partire da questa conclusione, si è poi divertito a capire come applicare il principio a un problema particolare, riprendendo da dove aveva interrotto suo padre.
Un paio di decenni fa, Steve Cook avanzò alcune ipotesi sulla quantità di memoria di cui un algoritmo aveva bisogno per risolvere un problema, affinandolo al minimo assoluto.
Nel 2019, James, insieme a Ian Mertz, uno dei dottorandi di Pitassi, sviluppò l’idea di prendere in prestito la memoria e dimostrò che ne sarebbe servita di meno. Il risultato non arrivò a confutare la congettura di suo padre, ma ha comunquerappresentato un piccolo progresso nella ricerca sulla teoria della complessità.
I problemi in questo settore, osserva James, a volte hanno un effetto domino: la soluzione di uno tira dietro di sé tutti gli altri. I risultati rivoluzionari, i più importanti, provengono da una lunga serie di lavori, da molte persone diverse.
Lancia anche un avvertimento: mentre un algoritmo P = NP diabolicamente veloce sarebbe sconvolgente, c’è anche uno scenario in cui P = NP potrebbe essere una delusione. Potrebbe risultare che un algoritmo P in grado di risolvere il problema NP-completo è su una scala temporale, diciamo, di n^100. “Tecnicamente rientra in P: è un polinomio”, afferma James. “Ma n^100 è ancora molto poco pratico”, implicando in tal modo che qualsiasi problema complesso sarebbe ancora fuori portata per le scale temporali umane.
Tutto ciò, ovviamente, supponendo che si possa trovare l’algoritmo. Donald Knuth, un algoritmista di Stanford, negli ultimi anni ha cambiato idea. Asuo parere, P è effettivamente uguale a NP, ma probabilmente non saremo mai in grado di sfruttare a nostro vantaggio questo fatto perché in realtà non conosceremo nessuno degli algoritmi che funzionano.
Ci sono un numero sbalorditivo di algoritmi, spiega, ma la maggior parte di essi è al di là della nostra comprensione. Quindi, mentre alcuni ricercatori potrebbero insistere sul fatto che non esiste un algoritmo P = NP, Knuth sostiene che “è più probabile che nessun algoritmo in tempo polinomiale sarà mai definito da un programma”.
Per Papadimitriou, qualsiasi risposta estinguerebbe un’ossessione per tutta la vita. Crede che il problema P vs. NP appartenga al regno degli enigmi scientifici fondamentali come l’origine della vita e l’unificazione dei campi di forza della natura. È il tipo di puzzle profondo e consequenziale, “concreto ma universale”, ha detto, “che aggiunge significato non solo alla scienza, ma alla stessa vita umana”.
Immagine: Il problema dell’albero di Steiner: collegare un insieme di punti con segmenti la cui lunghezza totale sia minima. Derek Brahney
(rp)
