Il problema di 50 anni che sfugge all'informatica teorica

Una soluzione a P vs NP potrebbe sbloccare innumerevoli problemi di calcolo o tenerli per sempre fuori portata.

Il problema dell'albero di Steiner: collegare un insieme di punti con segmenti di linea di lunghezza totale minima. Derek Brahney

di

• Siobhan Roberts pagina di archivio

27 ottobre 2021

uno. Lunedì 19 luglio 2021, nel mezzo di un'altra strana estate pandemica, uno scienziato informatico di spicco nel campo della teoria della complessità ha twittato un messaggio di servizio pubblico su un pasticcio amministrativo in un giornale. Ha firmato con un molto carico

Felice lunedi.

Questa storia faceva parte del nostro numero di novembre 2021

• Vedi il resto del problema
• sottoscrivi

In un universo parallelo, potrebbe essere stato davvero un lunedì molto felice. Una prova era apparsa online sulla stimata rivista ACM Transactions on Computational Theory, che vende eccezionali ricerche originali che esplorano i limiti del calcolo fattibile. Il risultato pretendeva di risolvere il problema di tutti i problemi: il Santo Graal dell'informatica teorica, del valore di un milione di dollari in premio e una fama che rivaleggiava per sempre con quella di Aristotele.

Questo prezioso problema, noto come P contro NP, è considerato allo stesso tempo il più importante nell'informatica teorica e nella matematica e completamente fuori portata. Affronta le domande centrali per la promessa, i limiti e le ambizioni del calcolo, chiedendo:

Perché alcuni problemi sono più difficili di altri?

Quali problemi possono risolvere realisticamente i computer?

Quanto tempo ci vorrà?

Ed è una ricerca con grandi guadagni filosofici e pratici.

Guarda, questa domanda P contro NP, cosa posso dire? Scott Aaronson, uno scienziato informatico dell'Università del Texas ad Austin, ha scritto nel suo memoria di idee , Il calcolo quantistico da Democrito . Alla gente piace descriverlo come 'probabilmente il problema centrale irrisolto dell'informatica teorica'. È un eufemismo comico. P vs NP è una delle domande più profonde che gli esseri umani si siano mai posti.

Un modo per pensare ai protagonisti di questa storia è il seguente:

P rappresenta i problemi che un computer può risolvere facilmente.

NP rappresenta problemi che, una volta risolti, sono facili da controllare, come i puzzle o il Sudoku. Molti problemi di NP corrispondono ad alcuni dei problemi 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 essere risolti con un algoritmo in un ragionevole lasso di tempo, se solo si potesse trovare l'algoritmo giusto e diabolicamente veloce? Se è così, molti problemi difficili sono improvvisamente risolvibili. E le loro soluzioni algoritmiche potrebbero portare a cambiamenti sociali di proporzioni utopiche: in medicina, ingegneria ed economia, biologia ed ecologia, neuroscienze e scienze sociali, industria, arti, persino politica e oltre.

A volte le classificazioni si evolvono: i problemi difficili si rivelano facili quando i ricercatori trovano soluzioni più efficienti. Testare se un numero è primo, ad esempio, è noto per essere nella classe NP dalla metà degli anni '70. Ma nel 2002, tre informatici dell'Indian Institute of Technology Kanpur hanno escogitato una prova incondizionata e un algoritmo intelligente che alla fine ha confermato che il problema era anche in P.

Se tutto i problemi complicati potrebbero essere trasformati con un tale gioco di prestigio algoritmico, le conseguenze per la società, per l'umanità e il nostro pianeta, sarebbero enormi.

Per cominciare, i sistemi di crittografia, la maggior parte dei quali sono basati su problemi NP, verrebbero violati. Avremmo bisogno di trovare un approccio completamente diverso per inviare comunicazioni sicure. Il ripiegamento delle proteine, una grande sfida in biologia di 50 anni, diventerebbe più trattabile, sbloccando nuove capacità per progettare farmaci che curano o curano malattie e scoprire enzimi che abbattono i rifiuti industriali. Significherebbe anche trovare soluzioni ottimali ai difficili problemi quotidiani, come tracciare un viaggio su strada per raggiungere tutte le destinazioni con una guida minima o far sedere gli invitati al matrimonio in modo che solo gli amici condividano lo stesso tavolo da pranzo.

Dall'inizio del problema P vs. NP 50 anni fa, emergente dall'importante intersezione tra logica matematica e tecnologia di calcolo elettronico, i ricercatori di tutto il mondo hanno fatto tentativi erculei di soluzione. Alcuni scienziati informatici hanno suggerito che gli sforzi potrebbero essere paragonati meglio a quelli di Sisifo, che lavorò senza risoluzione. Ma mentre coloro che per primi hanno esplorato il problema stanno finendo il tempo per vedere una soluzione, le nuove generazioni stanno felicemente affrontando la ricerca.

Per Manuel Sabin, uno scienziato informatico che sta finendo un dottorato di ricerca alla UC Berkeley, il fascino sta nel sondare l'impossibilità di problemi di cui non conoscerai la risposta fino a quando il sole non inghiottirà la terra. La ricerca potrebbe essere donchisciottesca, ma Sabin si sarebbe pentito di non essersi sbilanciato su questi mulini a vento.

Timothy Gowers, matematico dell'Università di Cambridge, la definisce una delle mie malattie matematiche personali. Ha perso l'estate del 2013 per l'inseguimento, dopo aver chiesto agli studenti un saggio sull'argomento in un test. Come ha raccontato sul suo blog: dopo aver segnato i saggi a giugno, ho pensato di passare un'ora o due a pensare di nuovo al problema, e quell'ora o due si è accidentalmente trasformata in circa tre mesi.

Il problema del commesso viaggiatore: trovare il percorso più breve possibile che visiti ogni città una volta, tornando infine alla città di origine.

DEREK BRAHNEY

La ricerca ha persino sconcertato lo scienziato informatico dell'Università di Toronto Stephen Cook, che ha inquadrato il problema e ha lanciato il campo della complessità computazionale con un articolo fondamentale nel 1971. Per questo lavoro, ha vinto il Premio Turing, l'equivalente del Premio Nobel per l'informatica. Ma non ha avuto fortuna a trovare una soluzione. Cook dice di non aver mai avuto buone idee: è semplicemente troppo difficile.

Due. Michael Sipser, uno scienziato informatico del MIT, stima di aver dedicato, tutto sommato, fino a un decennio sul problema. Si è interessato durante la scuola di specializzazione negli anni '70 e ha scommesso al suo compagno di studi Len Adleman un'oncia d'oro che sarebbe stato risolto entro la fine del secolo (Sipser ha pagato).

Negli anni '80, ha ottenuto un buon risultato risolvendo una versione del problema con un modello computazionale ristretto, portando a un periodo entusiasmante sul campo con diversi bei risultati, dando motivo di speranza che una soluzione potrebbe non essere troppo lontana.

Sipser torna ancora sul problema ogni tanto, ed è un ambasciatore risoluto, che tiene innumerevoli discorsi sull'argomento.

Il modo in cui entra in una spiegazione accessibile di P vs. NP è con un problema di moltiplicazione di base: 7 × 13 = ?

La risposta, 91, è abbastanza facile da calcolare nella tua testa. Sebbene moltiplicare numeri più grandi non sia così facile, un computer non richiederebbe praticamente tempo.

Ma capovolgere quei problemi è un'altra questione. Si consideri, ad esempio, trovare i due numeri primi di 97 cifre che si moltiplicano per produrre questo numero molto grande:

5003588856 0437213507 310 7418240490 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 80 processori ci sono voluti cinque mesi di elaborazione continua, spiega Sipser, che si traduce in 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 qui è, hai davvero bisogno di cercare? dice Sipser. O c'è un modo per risolvere il problema del factoring che ingrandisce rapidamente la risposta senza cercare? Non sappiamo la risposta a questa domanda.

Domande come questa entrano nel cuore della complessità computazionale, un campo pieno di problemi bestiali che i ricercatori stanno cercando di capire. Aaronson ha assemblato un Complexity Zoo, un catalogo online con 545 classi di problemi (e il conteggio). Ciascuno è classificato in base alla sua complessità, o difficoltà, e alle risorse (tempo, memoria, energia) necessarie per trovare soluzioni. P e NP sono le principali attrazioni.

Per fortuna scientifica, un matematico sovietico, Leonid Levin, convergeva su un risultato equivalente a quello di Cook più o meno nello stesso momento.

P è la classe che ha dato inizio a tutto. È 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 del tempo polinomiale, n è la dimensione dell'input e la crescita rispetto a quell'input avviene a un ritmo ragionevole (in questo caso, alla potenza di due).

Al contrario, alcuni problemi di hard NP 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 con la diffusione di covid). NP, come la descrive Aaronson, è la classe delle speranze infrante e dei sogni oziosi. Tuttavia, è pronto a chiarire un malinteso comune: non tutti i problemi di NP sono difficili. La classe NP contiene infatti la classe P, perché i problemi con soluzioni facili sono, ovviamente, anche facili da controllare.

I problemi più impegnativi di NP hanno spesso applicazioni pratiche importanti. Per questi problemi, un'esaustiva ricerca con la forza bruta di una soluzione probabilmente andrebbe avanti per un tempo impraticabilmente lungo - tempo geologico - prima di produrre una risposta. Se un algoritmo di ricerca a forza bruta è il miglior algoritmo possibile, allora P non è uguale a NP.

E tra i cognoscenti, questo è a quanto pare il consenso, che alcuni paragonano di più al credo religioso: P ≠ NP. La maggior parte concede solo un briciolo di speranza che si dimostrerà vero il contrario. Darei una probabilità dal 2 al 3% che P sia uguale a NP, dice Aaronson. Queste sono le quote di scommessa che prenderei.

Il risultato pubblicato a luglio ha presentato una prova esattamente di quel tiro lungo. Ma era solo l'ultima di una lunga tradizione di prove che non passavano d'occhio. Entro un giorno dalla pubblicazione, in una svolta di eventi degna dei Monty Python, il giornale è stato rimosso dal giornale online; poi sembrò riapparire brevemente prima di scomparire definitivamente. Era la versione più recente di un articolo che l'autore aveva pubblicato più di 60 volte sul server di prestampa di arXiv nell'ultimo decennio. Il redattore capo della rivista ha spiegato su Twitter che il risultato era stato respinto, ma in un caso di errore umano, la disposizione del giornale era in qualche modo cambiata da rifiuto ad accettare e la prova era arrivata alla pubblicazione.

3. All'inizio di agosto, quando ho incontrato Steve Cook nel suo ufficio nel campus, non aveva né visto né sentito parlare di quell'ultimo snafu a prova di P contro NP. Ora 81enne, era andato in pensione solo di recente, poiché la sua memoria stava venendo meno. Ecco perché abbiamo James qui, ha detto: suo figlio James, 36 anni, anche lui informatico, si è unito a noi per la mia visita. Steve stava sgomberando il suo ufficio. Al centro della stanza c'era un gigantesco cestino per la raccolta differenziata, che si stava riempiendo di vecchi numeri ingialliti del Journal of Symbolic Logic, una pila di enormi elenchi telefonici di Toronto in attesa nelle vicinanze.

Nel corso degli anni, Cook ha visto molte prove che pretendevano di risolvere il problema P vs. NP. Nel 2000, dopo che il Clay Mathematics Institute lo definì uno dei sette problemi irrisolti del millennio (ciascuno del valore di un milione di dollari in premio), fu inondato di messaggi di persone che pensavano di aver trionfato. Tutti i risultati erano sbagliati, se non semplicemente falsi. Circa la metà ha affermato di aver dimostrato che P è uguale a NP; l'altra metà è andata nella direzione opposta. Non molto tempo fa, una persona ha affermato di aver dimostrato entrambe le cose.

Cook, nel suo articolo del 1971, ipotizzò che P non fosse uguale a NP (lo espresse usando una terminologia diversa comune all'epoca). Da allora ha investito una quantità significativa, anche se indeterminata, di tempo lavorando per stabilire che è così. Non ho un buon ricordo di aver lavorato duramente, dice, ma i suoi colleghi ricordano che ogni volta che entravano nel dipartimento nel fine settimana, Steve era lì nel suo ufficio.

A meno che non stia gareggiando con le barche a vela, Cook non è uno che ha fretta; gli piace dare un'idea del tempo. E i suoi ex studenti ricordano una netta mancanza di spavalderia. La scienziata informatica Anna Lubiw, dell'Università di Waterloo, afferma che quando insegnò il teorema di Cook, parte di quel documento pionieristico, non lo chiamò mai come tale e non diede mai alcun indizio sul fatto che fosse lui la persona che lo ha dimostrato. Maria Klawe, matematica e scienziata informatica e presidente dell'Harvey Mudd College, dice che correggeva regolarmente Cook quando si perdeva insegnando prove che conosceva a fondo: si bloccava e diceva: 'Va bene. Dimmi come vanno le prove.' Cook è stato anche notoriamente modesto nelle domande di sovvenzione e nei rapporti relativi alla sua ricerca - confesserebbe: Onestamente, ho fatto pochi progressi ...

Storia correlata

L'evoluzione dell'informatica Calcolare i livelli di energia di un atomo di elio nel 1958 era molto più difficile di quanto non lo sia oggi. Ma un confronto tra i metodi di allora e quelli di oggi rivela alcune anomalie controintuitive sull'impatto dell'informatica.

Ha fatto progressi, tuttavia, nel reclutare James per sostenere la causa. All'inizio, James mostrò interesse per la matematica e l'informatica: all'età di nove anni esortò suo padre a insegnargli l'algebra booleana e la logica. Un paio di anni fa, dopo aver conseguito un dottorato di ricerca a Berkeley e aver lavorato in Google, è partito come ricercatore indipendente concentrandosi su progetti vari, alcuni dei quali indirettamente collegati a P vs. NP. E nonostante il track record, James, che ha una sorprendente somiglianza con suo padre, è imperterrito per aver ereditato una ricerca così apparentemente interminabile. Lo considera come farebbe con qualsiasi sforzo matematico: è un puzzle divertente. Ci deve essere una risposta a queste domande, dice. Ed è come, andiamo, qualcuno deve risolverlo. Cerchiamo solo di capire questo. È passato molto tempo. È imbarazzante non sapere ancora la risposta.

La mancanza di progressi non ha impedito a questa comunità di felici Sisifei di celebrare il 50° anniversario della complessità computazionale. I festeggiamenti sono iniziati nel 2019, quando devoti di tutto il mondo si sono riuniti al Fields Institute for Research in Mathematical Sciences, presso l'Università di Toronto, per un simposio in onore di Cook. Christos Papadimitriou, uno scienziato informatico della Columbia University che ha trascorso gran parte della sua carriera lavorando su P vs. NP, ha aperto l'evento con una conferenza pubblica, guardando indietro non di mezzo secolo ma di millenni.

Iniziò descrivendo ricerche secolari di soluzioni, utilizzando strumenti algebrici o riga e compasso, che considerava forme rudimentali di calcolo. Il racconto di Papadimitriou alla fine arrivò ad Alan Turing, il matematico britannico il cui articolo del 1936 On Computable Numbers formalizzava le nozioni di algoritmo e calcolo. Turing ha anche mostrato, con la sua idea di una macchina informatica universale, che non esiste un modo meccanico (cioè eseguito da una macchina) per dimostrare la verità o la falsità delle affermazioni matematiche; nessun modo sistematico per distinguere il dimostrabile dall'indimostrabile.

Papadimitriou ha affermato di considerare il documento di Turing il certificato di nascita dell'informatica e il certificato di nascita afferma che l'informatica è nata con una profonda comprensione dei propri limiti. Riteneva che l'informatica sia l'unico campo conosciuto del discorso scientifico nato con una tale consapevolezza, al contrario di altre scienze, che comprendono i propri limiti, come il resto di noi, nella tarda mezza età.

Non passò molto tempo dopo che le idee di Turing (e idee simili di altri) trovarono l'incarnazione nei primi computer che gli scienziati affrontarono domande sulle capacità e sui limiti intrinseci delle macchine. All'inizio degli anni '50, John von Neumann, il pioniere ungherese-americano del computer moderno, si vantava di un algoritmo del suo essere polinomiale, rispetto all'incumbent esponenziale, come ricorda Papadimitriou: aveva superato in astuzia un algoritmo lento con uno veloce. Questa fu l'alba di una nuova teoria: la teoria della complessità computazionale. Il punto cruciale era che solo gli algoritmi polinomiali sono in qualche modo validi o pratici o vale la pena mirare a un problema, mentre un algoritmo esponenziale, ha detto Papadimitriou, è l'equivalente algoritmico della morte.

Cook iniziò a pensare alla complessità per la prima volta a metà degli anni '60. Mentre lavorava al suo dottorato di ricerca ad Harvard, ha riflettuto sulla possibilità di dimostrare, dati alcuni modelli computazionali, che la moltiplicazione è più difficile dell'addizione (rimane un problema aperto).

Nel 1967, secondo un libro su Cook pubblicato dall'Association for Computing Machinery (ACM), mentre era post-dottorato a Berkeley, redasse appunti del corso che contenevano il seme del suo grande risultato. Aveva elaborato una formulazione delle classi di complessità che divennero note come P e NP e pose la domanda se P fosse uguale a NP. (Più o meno nello stesso periodo, altri, incluso lo scienziato informatico Jack Edmonds, ora in pensione dall'Università di Waterloo, stavano girando intorno alle stesse idee.)

Ma il campo dell'informatica era appena agli inizi 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 è stato preso in considerazione per un incarico ma non gli è stato offerto un posto. Aveva avvocati nel nuovo dipartimento di informatica dell'università e fecero pressioni affinché gli venisse concesso un posto nei loro ranghi, ma il preside non era incline a dare incarico a qualcuno che gli illustri matematici avevano negato.

La maggior parte dei teorici della complessità sogna un po' meno, optando invece per approcci indiretti.

Nel 1970, Cook si trasferì all'Università di Toronto. L'anno successivo pubblicò la sua svolta. Presentato a un simposio dell'ACM tenutosi a maggio a Shaker Heights, Ohio, il documento ha affinato il concetto di complessità e definito un modo per caratterizzare i problemi più difficili in NP. Dimostrò, in un lampo di alchimia algoritmica, che un problema, noto come problema di soddisfacibilità (ricerca di una soluzione per una formula data un insieme di vincoli), era in un certo senso il problema più difficile in NP, e che tutti gli altri problemi NP potrebbe essere ridotto ad esso.

Questo era un teorema cruciale: se esiste un algoritmo tempo-polinomiale che risolve il problema di soddisfacibilità, allora quell'algoritmo fungerà da chiave di scheletro, 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 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. Sebbene ci fossero corsi e lauree in questo campo alle prime armi, ha detto, sembrava effimero, forse privo di un profondo contenuto intellettuale. Era una seria preoccupazione per le persone che facevano informatica in quel momento, ha detto. Hanno chiesto: 'Questo è un campo? Dove sta andando?' Un giorno, Valiant si imbatté nel giornale di Cook. L'ha letto durante la notte. Mi sono trasformato, ha detto. In un attimo, le mie preoccupazioni per l'informatica si sono molto ridotte. Questo documento, per me, ha davvero fatto il campo. Penso che abbia reso l'informatica, l'abbia trasformata in qualcosa di sostanziale.

E poi, come racconta la storia, dopo il teorema di Cook venne un diluvio.

Nel 1972, Dick Karp, uno scienziato informatico a Berkeley, dopo aver letto l'articolo esoterico di Cook, dimostrò che molti dei classici problemi computazionali con cui era intimamente familiare, in sostanza ogni problema che non sapeva come risolvere, tratto dalla 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 ha riscontrato 21 problemi, tra cui il problema dello zaino (cercando il modo ottimale per imballare uno spazio limitato con gli oggetti di maggior valore), il problema del commesso viaggiatore (trovare il percorso più breve possibile che visiti ogni città una volta e ritorni in città di origine) e il problema dell'albero di Steiner (che cerca di collegare in modo ottimale un insieme di punti con segmenti di linea di lunghezza totale minima).

Karp ha mostrato che questa speciale raccolta di problemi era tutta equivalente, il che a sua volta ha dimostrato che il modello identificato da Cook non era un fenomeno isolato, ma piuttosto una metodologia di classificazione di potenza e portata sorprendenti. Era una specie di cartina di tornasole, identificando la classe di quelli che divennero noti come problemi NP-completi: una soluzione a qualsiasi li avrebbe risolti tutti.

Papadimitriou considera la NP-completezza uno strumento versatile. Se non riesci a risolvere un problema, prova a dimostrare che è NP-completo, perché questo forse ti farà risparmiare un sacco di tempo, ha detto durante la conferenza pubblica: puoi rinunciare a una soluzione esatta e passare alla risoluzione di un'approssimazione o invece variazione del problema.

Nella grande ondata della storia, Papadimitriou vede il fenomeno della NP-completezza e la ricerca P vs. NP come il destino dell'informatica. Perché, per fortuna scientifica, un matematico sovietico, Leonid Levin, convergeva su un risultato equivalente a quello di Cook più o meno nello stesso momento. Levin, ora alla Boston University, ha svolto il suo lavoro dietro la cortina di ferro. Dopo aver ricevuto una maggiore attenzione (emigrò in America nel 1978), il risultato divenne noto come il teorema di Cook-Levin.

E in un'altra coda, circa un decennio dopo, negli archivi di Princeton fu scoperta una lettera perduta del logico austriaco Kurt Gödel. Nel 1956 aveva scritto a von Neumann chiedendogli se un problema logico, che nel linguaggio moderno sarebbe chiamato NP-completo, potesse essere risolto in tempo polinomiale. Ha ritenuto che ciò avrebbe conseguenze della massima portata.

Il problema della cricca: cercare le cricche in un grafico, ad esempio un determinato sottoinsieme di amici in un social network.

DEREK BRAHNEY

Quattro. Mentre mezzo secolo di lavoro non ha prodotto nulla di vicino a una soluzione, alcuni risultati catturano almeno l'immaginazione: un articolo nel 2004 ha affermato una prova per P = NP utilizzando bolle di sapone come meccanismo di calcolo analogico (pellicola di sapone, naturalmente allineandosi nella configurazione a energia minima, risolve il problema dell'albero di Steiner NP-completo in un certo senso).

In questi giorni è un raro uccello di uno scienziato informatico, ad esempio Ron Fagin, un collega IBM, che affronta il problema a testa alta. Negli anni '70 ha prodotto il teorema di Fagin, che ha caratterizzato la classe NP in termini di logica matematica. E ha risolto il problema più di una volta, ma i risultati non sono mai rimasti per più di qualche giorno prima che trovasse un bug. Fagin ha recentemente ottenuto finanziamenti per un progetto P vs. NP dal programma Exploratory Challenges di IBM a sostegno della ricerca avventurosa. Nello spiegare perché continua a farlo, gli piace citare Theodore Roosevelt, il quale disse che è molto meglio osare cose potenti che classificarsi tra coloro che vivono in un grigio crepuscolo che non conosce né vittoria né sconfitta.

Ma la maggior parte dei teorici della complessità sogna un po' più in piccolo, optando invece per approcci indiretti: inclinare il problema, rimodellarlo o riformularlo, esplorare ambienti correlati e ridurre ulteriormente l'arsenale di strumenti che potrebbero essere schierati contro di esso (molti sono ora noti per essere inutili ).

Ryan Williams, uno scienziato informatico del MIT, sta cercando di illuminare il problema sia dall'alto che dal basso, studiando la natura dei limiti superiori e inferiori sui problemi computazionali fondamentali. Un limite superiore, in parole povere, è una specifica affermazione matematica che esiste un algoritmo concreto che risolve un problema particolare senza superare una certa quantità di risorse (tempo, memoria, energia). Un limite inferiore è l'opposto intangibile: è un'affermazione generale di impossibilità, che mostra che nessun algoritmo del genere esiste universalmente. Uno degli obiettivi della ricerca di Williams è rendere costruttivi e concreti i limiti inferiori: oggetti matematici con caratteristiche descrivibili. Crede che approcci più costruttivi ai limiti inferiori siano esattamente ciò che ci manca dagli attuali approcci nella teoria della complessità.

Williams ha fissato la probabilità che P ≠ NP a un 80% abbastanza moderato. Ma ultimamente alcuni ricercatori del settore esprimono dubbi anche su quel livello di certezza. Sempre di più, comincio a chiedermi se P sia uguale a NP, dice Toniann Pitassi, informatico dell'Università di Toronto ed ex dottorando di Cook, dice. Il suo approccio per aggirare il problema è quello di studiare sia analoghi in scala che in scala ridotta, modelli più difficili e più facili. A volte generalizzare la domanda lo rende più chiaro, dice. Ma nel complesso, non ha raggiunto la chiarezza: la maggior parte delle persone pensa che P non sia uguale a NP. E non lo so. Forse sono solo io, ma sento che è diventato sempre meno chiaro che questa è la verità.

Storicamente, sottolinea Pitassi, occasionalmente risultati sorprendenti sono emersi dal nulla, apparentemente impossibili dimostrati possibili da progettisti di algoritmi intelligenti. Lo stesso potrebbe accadere con P vs. NP, forse tra altri 50 anni o un secolo. Uno dei risultati più importanti in tutta la teoria della complessità, ad esempio, è stato ottenuto da David Barrington, dell'Università del Massachusetts, ad Amherst, nel 1989. Il succo di tutto ciò (per i nostri scopi) è che ha ideato un algoritmo intelligente, che si proponeva di fare qualcosa che apparentemente avrebbe dovuto richiedere una quantità illimitata di memoria, ma in realtà ne utilizzava una quantità sorprendentemente piccola: 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, ha colto di sorpresa James Cook. Attingendo dal teorema di Barrington, usa la memoria in un modo meravigliosamente strano. Come accennato nel titolo dell'articolo, da Harry Buhrman dell'Università di Amsterdam e collaboratori, si tratta di informatica con una memoria piena. James può snocciolare il paragrafo introduttivo del giornale praticamente alla lettera:

Immagina il seguente scenario. Vuoi eseguire un calcolo che richiede più memoria di quella che hai attualmente disponibile sul tuo computer. Un modo per affrontare questo problema è installare un nuovo disco rigido. A quanto pare hai un disco rigido ma è pieno di dati, immagini, filmati, file, ecc. Non è necessario accedere a quei dati al momento ma non vuoi nemmeno cancellarli. Puoi utilizzare il disco rigido per i tuoi calcoli, eventualmente alterandone temporaneamente il contenuto, garantendo che una volta completato il calcolo, il disco rigido torni al suo stato originale con tutti i dati intatti?

La risposta, controintuitivamente, è sì.

James lo considera un ricordo preso in prestito. Dopo che lo shock di questo risultato è sprofondato, si è divertito a capire come applicarlo a un problema particolare, riprendendo da dove aveva interrotto suo padre.

Un paio di decenni fa, Steve Cook è passato ad altri problemi correlati nella teoria della complessità. Con un problema, ha fatto una congettura sulla quantità di memoria di cui un algoritmo avrebbe bisogno per risolvere il problema, perfezionandolo al minimo assoluto. Nel 2019, James, insieme a Ian Mertz, uno dei dottorandi di Pitassi, ha implementato l'idea poetica di prendere in prestito la memoria e ha dimostrato che era necessaria ancora meno memoria. Il risultato non è andato fino in fondo per confutare la congettura di suo padre, ma è comunque un po' di progresso nella ricerca della grande complessità.

E i problemi nella teoria della complessità, osserva James, a volte hanno un effetto domino: se c'è una prova in un angolo critico, allora tutti i domino cadono. I risultati rivoluzionari, i più importanti, provengono da una lunga serie di lavoro, da parte di molte persone diverse, facendo progressi incrementali e stabilendo connessioni tra domande diverse, fino a quando alla fine emerge un grande risultato.

Menziona anche un avvertimento: mentre un algoritmo P = NP veramente 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 si trova su una scala temporale di, diciamo, n ^100. Tecnicamente rientra in P: è un polinomio, dice James. Ma n ^ 100 è ancora molto poco pratico: significherebbe che qualsiasi problema considerevole sarebbe ancora fuori portata su scale temporali umane.

Cioè, ovviamente, supponendo che possiamo trovare l'algoritmo in primo luogo. Donald Knuth, un algoritmista di Stanford, negli ultimi anni ha cambiato idea, ha cambiato idea. La sua intuizione è che P sia effettivamente uguale a NP, ma che probabilmente non saremo mai in grado di sfruttare questo fatto, in pratica, perché in realtà non conosceremo nessuno degli algoritmi che funzionano. Ci sono numeri sbalorditivi di algoritmi là fuori, spiega, ma la maggior parte di essi è al di là della nostra comprensione. Quindi, mentre alcuni ricercatori potrebbero insistere sul fatto che non esiste alcun algoritmo P = NP, Knuth sostiene che è più probabile che nessun algoritmo del tempo polinomiale sarà mai incarnato - in realtà scritto come un programma - da semplici mortali.

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.

Immagina di essere fortunati e di essere in grado di spremere altri duemila anni da questo pianeta, contro ogni probabilità e nonostante le stranezze, ha detto. E non risolviamo questi problemi. Qual e il punto?!