Il viaggio di 50 anni della teoria della complessità ai limiti della conoscenza | Rivista Quanta

Nella prima settimana del semestre autunnale del 2007, Marco Carmosino si è trascinato in un corso di matematica obbligatorio per tutti i laureati in informatica all'Università del Massachusetts, Amherst. Carmosino, al secondo anno, stava pensando di abbandonare il college per progettare videogiochi. Quindi il professore ha posto una semplice domanda che avrebbe cambiato il corso della sua vita: come fai a sapere che la matematica funziona davvero?

"Questo mi ha fatto sedere e prestare attenzione", ha ricordato Carmosino, ora scienziato informatico teorico presso IBM. Si iscrisse a un seminario facoltativo sull'opera di Kurt Gödel, le cui vertiginose argomentazioni autoreferenziali rivelarono per la prima volta i limiti del ragionamento matematico e gettarono le basi per tutti i lavori futuri sui limiti fondamentali del calcolo. Era molto da accettare.

"Non ho capito al 100%", ha detto Carmosino. "Ma sapevo che volevo farlo."

Oggi, anche i ricercatori esperti trovano scarsa comprensione quando affrontano la questione centrale aperta nell'informatica teorica, nota come problema P contro NP. In sostanza, questa domanda chiede se molti problemi computazionali a lungo considerati estremamente difficili possano effettivamente essere risolti facilmente (tramite una scorciatoia segreta che non abbiamo ancora scoperto) o se, come sospettano la maggior parte dei ricercatori, siano davvero difficili. In gioco c'è niente di meno che la natura di ciò che è conoscibile.

Nonostante decenni di sforzi da parte dei ricercatori nel campo della teoria della complessità computazionale - lo studio di tali domande sulla difficoltà intrinseca di diversi problemi - una soluzione alla questione P contro NP è rimasta sfuggente. E non è nemmeno chiaro dove dovrebbe iniziare una presunta prova.

"Non c'è una mappa stradale", ha detto Michael Sipser, un veterano teorico della complessità presso il Massachusetts Institute of Technology che negli anni '1980 ha trascorso anni alle prese con il problema. "È come se stessi andando nel deserto."

Sembra che dimostrare che i problemi computazionali sono difficili da risolvere sia di per sé un compito difficile. Ma perché è così difficile? E quanto è difficile? Carmosino e altri ricercatori nel sottocampo della meta-complessità riformulano domande come questa come problemi computazionali, spingendo il campo in avanti ribaltando la lente della teoria della complessità su se stessa.

“Potresti pensare, 'OK, è piuttosto figo. Forse i teorici della complessità sono impazziti'”, ha detto Raul Ilango, uno studente laureato al MIT che ha prodotto alcuni dei più entusiasmanti risultati recenti nel campo.

Studiando queste domande introspettive, i ricercatori hanno appreso che la durezza nel dimostrare la durezza computazionale è intimamente legata a domande fondamentali che a prima vista possono sembrare non correlate. Quanto è difficile individuare schemi nascosti in dati apparentemente casuali? E se esistono problemi veramente difficili, quanto spesso lo sono?

"È diventato chiaro che la meta-complessità è vicina al cuore delle cose", ha detto Scott Aaronson, un teorico della complessità presso l'Università del Texas, Austin.

Questa è la storia del lungo e tortuoso percorso che ha portato i ricercatori dal problema P contro NP alla meta-complessità. Non è stato un viaggio facile: il percorso è disseminato di false svolte e posti di blocco, e torna su se stesso ancora e ancora. Tuttavia, per i ricercatori della meta-complessità, quel viaggio in un paesaggio inesplorato è la sua stessa ricompensa. Inizia a fare domande apparentemente semplici, ha detto Kabanets di San Valentino, un teorico della complessità alla Simon Fraser University in Canada, e "non hai idea di dove andrai".

Sconosciuto noto

Il problema P contro NP deve il suo nome poco brillante all'abitudine dei teorici della complessità di ordinare i problemi computazionali in ampi “classi di complessità” con etichette che richiamano i simboli del ticker del Nasdaq. Un problema computazionale è un problema che in linea di principio può essere risolto da un algoritmo, un elenco di istruzioni specificato con precisione. Ma non tutti gli algoritmi sono ugualmente utili e la variazione tra algoritmi suggerisce differenze fondamentali tra problemi in classi diverse. La sfida per i teorici della complessità è trasformare questi accenni in teoremi rigorosi sulle relazioni tra classi di complessità.

Queste relazioni riflettono verità immutabili sul calcolo che vanno ben oltre qualsiasi tecnologia specifica. "Questo è come scoprire le leggi dell'universo", ha detto Kabanets.

“P” e “NP” sono i due membri più famosi di a serraglio in crescita di centinaia di classi di complessità. In parole povere, P è la classe di problemi che possono essere risolti facilmente, come l'alfabetizzazione di un elenco. NP è la classe dei problemi con soluzioni facilmente verificabili, come i sudoku. Poiché tutti i problemi facilmente risolvibili sono anche facili da controllare, i problemi in P sono anche in NP. Ma alcuni problemi NP sembrano difficili da risolvere: non puoi intuire immediatamente la soluzione di un sudoku senza prima provare molte possibilità. Potrebbe essere che questa apparente durezza sia solo un'illusione - che ci sia un solo semplice trucco per risolvere ogni problema facilmente controllabile?

Se è così, allora P = NP: le due classi sono equivalenti. Se è così, deve esserci qualche algoritmo che renda banale risolvere enormi sudoku, ottimizzare le rotte di spedizione globali, violare la crittografia all'avanguardia e automatizzare le dimostrazioni di teoremi matematici. Se P ≠ NP, allora molti problemi computazionali risolvibili in linea di principio rimarranno in pratica per sempre fuori dalla nostra portata.

I ricercatori si preoccupavano dei limiti del ragionamento matematico formale molto prima che il problema P contro NP fosse articolato per la prima volta, anzi, molto prima dell'inizio della moderna informatica. Nel 1921, alle prese con la stessa domanda che avrebbe attirato l'attenzione di Carmosino quasi un secolo dopo, il matematico David Hilbert propose un programma di ricerca per fondare la matematica sull'assoluta certezza. Sperava di partire da poche semplici ipotesi, chiamate assiomi, e derivare una teoria matematica unificata che soddisfacesse tre criteri chiave.

La prima condizione di Hilbert, la coerenza, era il requisito essenziale che la matematica fosse libera da contraddizioni: se due affermazioni contraddittorie potessero essere dimostrate partendo dagli stessi assiomi, l'intera teoria sarebbe irrecuperabile. Ma una teoria potrebbe essere esente da contraddizioni e ancora limitata nella sua portata. Questa era la motivazione per la seconda condizione di Hilbert, la completezza: il requisito che tutti gli enunciati matematici fossero dimostrabilmente veri o dimostrabilmente falsi. Il suo terzo criterio, la decidibilità, richiedeva una procedura meccanica inequivocabile per determinare se un'affermazione matematica fosse vera o falsa. Rivolgendosi a una conferenza nel 1930, Hilbert dichiarò: "Il nostro slogan sarà 'Dobbiamo sapere, lo sapremo'".

Solo un anno dopo, Gödel diede il primo colpo al sogno di Hilbert. Lui dimostrato che un'affermazione controproducente come "questa affermazione non è dimostrabile" potrebbe essere derivata da qualsiasi insieme appropriato di assiomi. Se una tale affermazione è davvero indimostrabile, la teoria è incompleta, ma se è dimostrabile, la teoria è incoerente - un risultato ancora peggiore. Nello stesso articolo, Gödel ha anche dimostrato che nessuna teoria matematica potrebbe mai dimostrare la propria coerenza.

I ricercatori nutrivano ancora la speranza che una futura teoria della matematica, sebbene necessariamente incompleta, potesse nondimeno dimostrarsi decidibile. Forse potrebbero sviluppare procedure che identificherebbero tutte le affermazioni dimostrabili evitando proposizioni irritanti come quella di Gödel. Il guaio era che nessuno sapeva ragionare su queste ipotetiche procedure.

Poi, nel 1936, uno studente laureato di 23 anni di nome Alan Turing ha riformulato la condizione di decidibilità di Hilbert nel linguaggio allora sconosciuto del calcolo e gli ha inferto un colpo fatale. Turing formulò un modello matematico, ora noto come il Macchina di Turing - che potrebbe rappresentare tutti i possibili algoritmi e ha mostrato che se la procedura di Hilbert esistesse, si adatterebbe a questo modello. Ha poi utilizzato metodi autoreferenziali come quello di Gödel dimostrare l'esistenza di affermazioni indecidibili o, equivalentemente, problemi non calcolabili che nessun algoritmo potrebbe risolvere.

Il programma di Hilbert era in rovina: ci sarebbero stati per sempre limiti fondamentali a ciò che poteva essere provato ea ciò che poteva essere calcolato. Ma quando i computer si sono evoluti da astrazioni teoriche a macchine reali, i ricercatori si sono resi conto che la semplice distinzione di Turing tra problemi risolvibili e irrisolvibili lasciava molte domande senza risposta.

Negli anni '1960, gli informatici avevano sviluppato algoritmi veloci per risolvere alcuni problemi, mentre per altri gli unici algoritmi conosciuti erano terribilmente lenti. E se la domanda non fosse solo se i problemi sono risolvibili, ma quanto sono difficili da risolvere?

"Emerge una ricca teoria e non conosciamo più le risposte", ha detto Carmosino.

Percorsi divergenti

Per illustrare quanto possano essere sconcertanti le domande sulla durezza, consideriamo un paio di problemi strettamente correlati che coinvolgono i grafici. Si tratta di reti di punti, chiamate nodi, collegate da linee, chiamate spigoli. Gli informatici li usano per modellare tutto da calcolo quantistico Vai all’email flusso di traffico.

Supponiamo che ti venga dato un grafico e ti venga chiesto di trovare qualcosa chiamato percorso hamiltoniano, un percorso che attraversa ogni nodo esattamente una volta. Questo problema è chiaramente risolvibile in linea di principio: esiste solo un numero finito di percorsi possibili, quindi se tutto il resto fallisce puoi semplicemente controllarli ciascuno. Va bene se ci sono solo pochi nodi, ma per grafici anche leggermente più grandi il numero di possibilità va fuori controllo, rendendo rapidamente inutile questo semplice algoritmo.

Esistono algoritmi di percorso hamiltoniani più sofisticati che combattono meglio, ma il tempo che gli algoritmi richiedono per risolvere il problema cresce invariabilmente in modo esponenziale con la dimensione del grafico. I grafici non devono essere molto grandi prima che anche i migliori algoritmi che i ricercatori hanno scoperto non riescano a trovare un percorso "in un ragionevole lasso di tempo", ha detto Russel Impagliazzo, un teorico della complessità presso l'Università della California, San Diego. "E per 'ragionevole quantità di tempo' intendo 'prima che l'universo finisca'".

Il problema del cammino hamiltoniano ha un'altra proprietà interessante. Se qualcuno afferma di aver trovato un cammino hamiltoniano su un particolare grafico, puoi verificare rapidamente se la soluzione è valida, anche se il grafico è molto grande. Tutto quello che devi fare è seguire il percorso e spuntare i nodi uno per uno, controllando di non aver spuntato nessun nodo due volte. Se alla fine non mancano nodi, allora il percorso è hamiltoniano.

Il tempo necessario per eseguire questo algoritmo di controllo della soluzione è proporzionale alla dimensione del grafico. Ciò lo colloca nella categoria più ampia degli algoritmi polinomiali, i cui tempi di esecuzione aumentano come funzioni polinomiali della dimensione del grafico. La crescita polinomiale è docile rispetto alla crescita esponenziale, quindi gli algoritmi polinomiali rimangono fattibili anche su grafici di grandi dimensioni. "È notevolmente più efficiente", ha detto Carmosino.

Il problema del percorso hamiltoniano presenta una netta asimmetria: puoi verificare una soluzione corretta utilizzando un algoritmo polinomiale veloce, ma per trovare una soluzione avrai bisogno di un algoritmo esponenziale lento. Questa asimmetria può non sembrare sorprendente - è più facile riconoscere un capolavoro artistico che crearne uno, più facile verificare una dimostrazione matematica che dimostrare un nuovo teorema - eppure non tutti i problemi computazionali hanno questo carattere asimmetrico. In effetti, un problema molto simile alla ricerca di cammini hamiltoniani si comporta in modo molto diverso.

Supponiamo che ti venga nuovamente fornito un grafico, ma ora ti viene chiesto di trovare un "percorso euleriano" che attraversi ogni bordo esattamente una volta. Di nuovo, c'è un algoritmo polinomiale per verificare le possibili soluzioni, ma questa volta c'è anche un algoritmo polinomiale per risolvere il problema. Nessuna asimmetria qui. Nella teoria della complessità, alcuni percorsi sembrano più facili da trovare rispetto ad altri.

Sia il problema del cammino hamiltoniano che il problema del cammino euleriano sono nella classe di complessità NP, definita per includere tutti i problemi le cui soluzioni possono essere controllate da algoritmi polinomiali. Anche il problema del cammino euleriano rientra nella classe P perché un algoritmo polinomiale può risolverlo, ma a quanto pare ciò non è vero per il problema del cammino hamiltoniano. Perché questi due problemi di grafi, così superficialmente simili, dovrebbero differire in modo così drammatico? Questa è l'essenza del problema P contro NP.

Universalmente difficile

All'inizio, le classi di complessità sembravano categorie convenienti per ordinare problemi simili ma non direttamente correlati: nessuno sospettava che trovare percorsi hamiltoniani avesse qualcosa a che fare con altri difficili problemi computazionali.

Poi nel 1971, entro un anno dal trasferimento all'Università di Toronto dopo che gli era stato negato il mandato negli Stati Uniti, il teorico della complessità Stefano Cook pubblicato un risultato straordinario. Ha identificato un particolare problema NP con una strana caratteristica: se esiste un algoritmo polinomiale in grado di risolvere quel problema, può anche risolvere ogni altro problema in NP. Il problema "universale" di Cook, sembrava, era una colonna solitaria che sosteneva la classe dei problemi apparentemente difficili, separandoli dai problemi facili sottostanti. Risolvi quell'unico problema e il resto di NP crollerà.

Cook sospettava che non esistesse un algoritmo veloce per il suo problema universale, e lo disse a metà del documento, aggiungendo: "Penso che valga la pena spendere uno sforzo considerevole per provare questa congettura". "Sforzo considerevole" risulterebbe essere un eufemismo.

Più o meno nello stesso periodo, uno studente laureato in Unione Sovietica di nome Leonid Levi dimostrato a risultato simile, tranne per il fatto che ha identificato diversi problemi universali diversi. Inoltre, il teorico americano della complessità Riccardo Karp dimostrato che la proprietà dell'universalità identificata da Cook (e da Levin, sebbene Karp e Cook conoscessero il lavoro di Levin solo anni dopo) fosse essa stessa quasi universale. Quasi tutti i problemi NP senza un noto algoritmo polinomiale, ovvero quasi tutti i problemi facilmente controllabili che sembravano difficili, avevano la stessa proprietà, che divenne nota come NP-completezza.

Ciò significa che tutti i problemi NP-completi: il problema del percorso hamiltoniano, il sudoku e migliaia di altri — sono in un senso preciso equivalenti. "Hai tutti questi diversi compiti naturali, e tutti magicamente si rivelano essere lo stesso compito", ha detto Ilango. "E ancora non sappiamo se lo stesso compito sia possibile o meno."

Stabilire la difficoltà di qualsiasi problema NP-completo sarebbe sufficiente per risolvere la questione P contro NP. Se P ≠ NP, la distinzione tra problemi facili e difficili è sostenuta da migliaia di colonne tutte ugualmente forti. Se P = NP, l'intero edificio sta barcollando sull'orlo del collasso, aspettando solo che cada un solo pezzo.

Cook, Levin e Karp avevano unificato quelli che sembravano molti problemi non correlati. Ora tutto ciò che i teorici della complessità dovevano fare era risolvere un problema: P = NP o no?

Cinquant'anni dopo, la domanda rimane senza risposta. Kabanets ha paragonato il ragionamento sui limiti del calcolo al rilevamento di un vasto territorio senza alcun senso del quadro generale. Un essere con un potere computazionale illimitato potrebbe scrutare dalla cima di una montagna e ammirare l'intero paesaggio in una volta, ma i comuni mortali non possono contare su quel tipo di vantaggio. "Quelli di noi in fondo alla montagna possono provare a saltare su e giù per una visione migliore", ha detto.

Supponiamo che P = NP. Per dimostrarlo, i ricercatori dovrebbero trovare un algoritmo veloce per un problema NP-completo, che potrebbe nascondersi in qualche angolo oscuro di quel vasto panorama. Non c'è alcuna garanzia che lo troveranno presto: i teorici della complessità hanno occasionalmente scoperto algoritmi ingegnosi per problemi apparentemente difficili (sebbene non NP-completi) solo dopo decenni di lavoro.

Supponiamo ora che P ≠ NP. Dimostrare che sembra ancora più difficile. I teorici della complessità dovrebbero stabilire che non potrebbe esistere alcun algoritmo veloce, anticipando e vanificando efficacemente i migliori sforzi di tutti i futuri ricercatori.

Non sapere da dove cominciare è parte del problema. Ma non è che i ricercatori non ci abbiano provato. Nel corso dei decenni hanno affrontato il problema da molte angolazioni e hanno trovato la strada bloccata a ogni svolta. "È una delle verità più palesi nell'informatica teorica", ha detto Carmosino. "Quando hai un fenomeno così durevole, vuoi una spiegazione."

All'ultimo anno di college di Carmosino, la sua curiosità lo aveva portato da Gödel a un corso di laurea in teoria della complessità. Fu sorpreso di rendersi conto che stava dedicando più tempo ai compiti che al suo progetto di passione, un programma per computer che avrebbe imparato la struttura narrativa delle fiabe e ne avrebbe generate di nuove.

"Ho pensato, 'Wow, devo prenderlo sul serio'", ha ricordato Carmosino. In poco tempo, fu così assorbito dall'argomento che il suo mentore gli suggerì gentilmente di riconsiderare i suoi piani post-laurea.

"Era tipo, 'Sai, se vuoi continuare a fare questo, se vuoi continuare a fare informatica teorica e teoria della complessità, puoi: si chiama scuola di specializzazione'", ha detto Carmosino. Dopo aver ottenuto il master, si è trasferito a San Diego nel 2012 per lavorare per un dottorato sotto la supervisione di Impagliazzo.

L'obiettivo principale di Carmosino, in un primo momento, era quello di comprendere meglio a carta di riferimento di due decenni prima che aveva catturato la sua immaginazione. Quel documento, dai teorici della complessità Aleksandr Razborov ed Stefano Rudich, aveva dimostrato che una certa strategia "naturale" per dimostrare P ≠ NP sarebbe quasi certamente fallita, perché il successo sarebbe arrivato a un costo elevato - il completo fallimento della crittografia - che i ricercatori consideravano molto improbabile. I ricercatori hanno interpretato il risultato di Razborov e Rudich come un ostacolo a questo approccio popolare per dimostrare P ≠ NP.

Questa "barriera delle prove naturali" è solo una delle tante barriere note alla risoluzione di problemi aperti nella teoria della complessità. Ognuno agisce come un posto di blocco, avvertendo che un percorso apparentemente promettente è in realtà un vicolo cieco. Insieme, queste barriere indicano che qualsiasi prova che risolva il problema P contro NP dovrebbe essere radicalmente diversa da qualsiasi cosa usata in passato; ecco perché la maggior parte dei ricercatori ritiene che una soluzione sia lontana. Ma almeno le barriere dicono loro dove non guardare.

"La teoria della complessità è sia maledetta che benedetta da così tante barriere", ha detto Ilango.

Quando Carmosino incontrò la barriera delle prove naturali, aveva quasi 20 anni. Ma sospettava che avesse più lezioni per i ricercatori. Quella sensazione un giorno sarebbe stata giustificata quando lui e tre colleghi hanno dimostrato un risultato sorprendente esaminando la barriera delle prove naturali dal punto di vista della meta-complessità. La loro dimostrazione è stata uno dei pochi risultati importanti che hanno suscitato un nuovo interesse per la meta-complessità, portando a una raffica di progressi negli ultimi anni.

Ma per seguire il percorso dalla barriera delle prove naturali alla meta-complessità, dovremo tornare al punto in cui abbiamo lasciato i ricercatori negli anni '1970, quando iniziarono ad affrontare il problema P contro NP. Cosa ha reso così difficile dimostrare che i problemi sono difficili?

Un percorso tortuoso

All'inizio, i ricercatori hanno provato a dimostrare P ≠ NP — cioè dimostrare che alcuni problemi NP non sono risolvibili con nessun algoritmo polinomiale possibile — usando variazioni sulle tecniche che Turing aveva usato per dimostrare che alcuni problemi non sono risolvibili con nessun algoritmo di sorta . Ma rapidamente scoperto una prova che quei metodi non avrebbero funzionato: il primo grande ostacolo alla risoluzione della questione P contro NP. Così iniziarono a cercare un altro approccio, e presto ne trovarono uno nell'opera del contemporaneo di Turing Claude Shannon.

Shannon, che è cresciuto in una piccola città nel nord del Michigan, sembrava una figura improbabile per inaugurare l'era dell'informazione. Eppure ha esemplificato la natura interdisciplinare della disciplina emergente dell'informatica, sentendosi ugualmente a suo agio nell'ingegneria elettrica e nella logica matematica. Nel suo tesi di master, Shannon ha mostrato come i circuiti fatti di interruttori elettromeccanici potrebbero rappresentare espressioni logiche che coinvolgono variabili booleane - quantità che possono assumere solo due valori (come vero o falso, o 1 e 0).

In queste espressioni le variabili booleane sono collegate tra loro dalle “porte logiche” AND, OR e NOT. L'espressione elementare A AND B, per esempio, è vera quando sia A che B sono vere, e falsa altrimenti; A OR B, invece, è vera se almeno una delle due variabili è vera. Una porta NOT è ancora più semplice: inverte il valore di una singola variabile. Con un numero sufficiente di questi blocchi di base, puoi eseguire qualsiasi calcolo.

“Quando guardi il tuo computer, alla fine della giornata, cosa sta facendo? Sta correndo un circuito”, ha detto Ilango.

Il lavoro di Shannon ha suggerito ai teorici un nuovo modo di pensare alla difficoltà dei problemi computazionali, chiamato "complessità dei circuiti", anche se i circuiti in questione sono solo astrazioni matematiche. Per un po', i ricercatori hanno pensato che questo approccio potesse essere il modo per risolvere P contro NP, ma alla fine la pista si è scontrata con la barriera delle prove naturali.

La struttura della complessità del circuito richiede di ripensare i concetti più basilari nel modello di calcolo di Turing. Qui, invece dei problemi computazionali e degli algoritmi che li risolvono, i ricercatori considerano le funzioni booleane ei circuiti che le calcolano. Una funzione booleana accetta variabili booleane - veri e falsi, 1 e 0 - e restituisce vero o falso, 1 o 0. E come un algoritmo, un circuito descrive una procedura per produrre un output dato qualsiasi input.

"La mia comprensione è che le persone hanno iniziato a lavorare sulla complessità dei circuiti perché hanno deciso che le macchine di Turing erano troppo complicate", ha detto Ryan Williams, un teorico della complessità al MIT. "Possiamo studiare i circuiti porta per porta".

Proprio come possono esserci molti algoritmi per risolvere un dato problema computazionale, alcuni più veloci di altri, molti circuiti diversi possono calcolare qualsiasi data funzione booleana, alcuni con meno porte di altri. I ricercatori definiscono la complessità del circuito di una funzione come il numero totale di porte nel circuito più piccolo che la calcola. Per una funzione con un numero fisso di variabili di ingresso, anche la complessità del circuito è un numero fisso, maggiore per alcune funzioni che per altre.

Ma in molti casi, puoi considerare versioni più complicate della stessa funzione aumentando il numero di variabili di input, così come puoi rendere più difficile il problema del percorso hamiltoniano considerando grafici più grandi. I ricercatori quindi considerano la stessa domanda che si pongono quando studiano i tempi di esecuzione degli algoritmi: il numero minimo di porte necessarie per calcolare una funzione booleana cresce in modo polinomiale o esponenziale all'aumentare del numero di variabili di input? I ricercatori chiamano queste due categorie di funzioni rispettivamente "facili da calcolare" e "difficili da calcolare".

Una funzione booleana facile da calcolare è simile a un problema computazionale nella classe P, che può essere risolto da un algoritmo che viene eseguito in tempo polinomiale. Ma ci sono anche funzioni analoghe ai problemi NP difficili, in cui il modo migliore che i ricercatori hanno scoperto per calcolare versioni progressivamente più grandi richiede un numero di porte in aumento esponenziale, ma la risposta può essere facilmente verificata. Se i teorici della complessità potessero dimostrare che non esiste davvero un modo migliore per calcolare una tale funzione, ciò implicherebbe P ≠ NP.

Questa era la strategia perseguita dalla maggior parte dei teorici della complessità negli anni '1980. E le probabilità erano dalla loro parte. Shannon aveva dimostrato nel 1949 che quasi ogni tabella di verità booleana (che è solo un lungo elenco di tutti i possibili input e output di una funzione booleana di dimensione fissa) ha una complessità del circuito praticamente la più alta possibile. Ha usato un argomento sorprendentemente semplice: ci sono molti meno modi per combinare un piccolo numero di porte rispetto a molti modi per combinare molte porte.

"Semplicemente non ci sono abbastanza piccoli circuiti per andare in giro", ha detto Aaronson.

Quindi i teorici della complessità si sono trovati in una situazione curiosa. Se quasi tutte le tabelle di verità hanno un'elevata complessità del circuito, allora quasi tutte le funzioni booleane devono essere difficili da calcolare. I ricercatori dovevano solo identificare una singola funzione di questo tipo che fosse anche nota per essere nella classe NP. Quanto può essere duro?

Cripto Bros

All'inizio i progressi furono rapidi. Nel 1981, Sipser e due collaboratori dimostrato che una certa funzione booleana era decisamente difficile da calcolare se usavano circuiti con certe restrizioni su come potevano essere disposte le porte.

"La fantasia era che saresti stato in grado di dimostrare cose su questi modelli limitati, e poi costruire su ciò che hai imparato a lavorare con sempre meno restrizioni", ha detto Sipser.

Nel 1985, Razborov fece il grande passo successivo. Aveva appena iniziato la scuola di specializzazione a Mosca e si è unito allo sforzo per caso mentre affrontava un problema in un'altra branca della matematica, dove si è scoperto che la risoluzione del problema P contro NP era un prerequisito.

"Sono stato semplicemente fortunato a non sapere quanto fosse difficile questo problema", ha detto Razborov. “Altrimenti forse non avrei nemmeno iniziato”.

Razborov ha analizzato circuiti contenenti solo porte AND e OR, e dimostrato che una particolare funzione era difficile da calcolare utilizzando tali circuiti, indipendentemente da come fossero disposte le porte - per di più, quella funzione era nota per essere NP-completa. Tutto ciò che i ricercatori dovevano fare per risolvere P contro NP era estendere le tecniche di Razborov ai circuiti con porte NOT.

"C'era una sorta di sensazione universale che un altro passo, un altro colpo, e ce la faremo", ha detto Razborov. Ma non è quello che è successo. Lo stesso Razborov ha dimostrato che il suo metodo fallirebbe se NOT gates venisse aggiunto al mix, e nessuno potrebbe trovare un'altra via da seguire. Con il passare degli anni, iniziò a chiedersi perché la pista si fosse esaurita.

Negli Stati Uniti, Rudich stava riflettendo sulla stessa domanda. Lui e Impagliazzo erano compagni di classe universitari che si erano diplomati insieme. La loro amicizia era stata innescata da un fascino condiviso per le dimostrazioni autoreferenziali di Gödel e Turing e le loro implicazioni per i fondamenti della matematica e dell'informatica.

"La nostra battuta era che avremmo ottenuto un pulsante che diceva 'autoreferenzialità'", ha detto Impagliazzo.

Come studenti laureati, sia Rudich che Impagliazzo hanno lavorato sui fondamenti teorici della complessità della crittografia, un argomento che offre forse la migliore motivazione pratica per tentare di dimostrare P ≠ NP. I crittografi nascondono i messaggi segreti ammantandoli di "pseudocasualità": un messaggio crittografato in questo modo sembrerà un miscuglio casuale di numeri a qualsiasi intercettatore, ma può comunque essere decodificato dal destinatario previsto. Ma come puoi essere sicuro che un aspirante intercettatore troverà troppo difficile decifrare il codice?

È qui che entra in gioco la teoria della complessità. I ​​metodi di crittografia più utilizzati oggi sono tutti basati su problemi NP apparentemente difficili: per decrittografare il messaggio, un utente malintenzionato avrebbe bisogno di un algoritmo veloce non ancora scoperto per risolvere il problema. Per stabilire che questi metodi sono veramente sicuri, una cosa che dovresti fare è dimostrare che P ≠ NP. Senza una prova, ha detto Sipser, tutto ciò che puoi fare è "sperare che chiunque tu stia cercando di mantenere il segreto non sia un matematico migliore di te".

Sebbene affascinante di per sé, la crittografia sembrava molto lontana dalle argomentazioni autoreferenziali che avevano inizialmente attirato Rudich e Impagliazzo sul campo. Ma mentre Rudich lottava per capire perché l'approccio alla complessità del circuito si fosse bloccato, iniziò a rendersi conto che i due argomenti non erano poi così distanti. La strategia che i ricercatori avevano adottato nei loro tentativi di dimostrare che P ≠ NP aveva un carattere controproducente che ricordava la famosa proposizione di Gödel "questa affermazione non è dimostrabile" - e la crittografia potrebbe aiutare a spiegare perché. In Russia, Razborov ha scoperto una connessione simile nello stesso periodo. Questi erano i semi della barriera delle prove naturali.

La tensione al centro della barriera delle prove naturali è che il compito di distinguere le funzioni ad alta complessità da quelle a bassa complessità è simile al compito di distinguere la vera casualità dalla pseudocasualità usata per crittografare i messaggi. Vorremmo dimostrare che le funzioni ad alta complessità sono categoricamente diverse dalle funzioni a bassa complessità, per provare P ≠ NP. Ma vorremmo anche che la pseudocasualità fosse indistinguibile dalla casualità, per essere fiduciosi nella sicurezza della crittografia. Forse non possiamo avere entrambe le cose.

Uno scherzo crudele

Nel 1994, Razborov e Rudich si sono resi conto di aver avuto intuizioni simili e hanno iniziato a lavorare insieme per combinare i loro risultati. Per prima cosa hanno osservato che tutti i precedenti tentativi di dimostrare P ≠ NP utilizzando la complessità del circuito avevano adottato la stessa strategia generale: identificare una proprietà speciale di una funzione booleana NP-completa, quindi dimostrare che nessuna funzione facile da calcolare potrebbe condividere quella proprietà. Ciò mostrerebbe che la funzione NP-completa scelta era davvero difficile da calcolare, dimostrando P ≠ NP.

Sipser, Razborov e altri avevano utilizzato con successo questa stessa strategia per dimostrare i loro risultati più limitati e, in ogni caso, la proprietà speciale identificata dai ricercatori era condivisa dalla maggior parte delle funzioni booleane. Razborov e Rudich hanno coniato il termine "prova naturale" per riferirsi a questo caso in cui la proprietà era ampiamente condivisa, semplicemente perché non c'erano alternative note. Se fossero possibili prove "innaturali", dovrebbero essere molto controintuitive e meritevoli di questo nome.

Razborov e Rudich hanno quindi dimostrato il loro risultato principale: una dimostrazione naturale di P ≠ NP richiederebbe una comprensione molto completa di come differiscono le funzioni facili da calcolare e quelle difficili da calcolare, e quella conoscenza potrebbe anche alimentare un algoritmo veloce per individuare facilmente -to-comput anche se sono superficialmente complicate. Se i teorici della complessità fossero riusciti in una dimostrazione naturale di P ≠ NP, avrebbero scoperto un modo quasi infallibile per dare un'occhiata a una tabella di verità arbitraria e determinare se la funzione corrispondente aveva una complessità di circuito alta o bassa - un risultato molto più forte e più generale di avevano deciso di dimostrare.

"Quasi non puoi fare a meno di ottenere più di quanto ti aspettavi", ha detto Carmosino.

È come se provassi a verificare un'affermazione specifica, ma ogni tentativo si trasforma in un progetto per un rilevatore di bugie generico: sembrerebbe troppo bello per essere vero. Per i teorici della complessità, anche il sorprendente potere delle prove naturali rendeva meno probabile il successo. Ma se una tale dimostrazione avesse avuto successo, le conseguenze inaspettate sarebbero state una cattiva notizia per la crittografia, a causa della connessione tra complessità del circuito e pseudocasualità.

Per comprendere questa connessione, immagina di guardare la colonna di output nella tabella di verità di una funzione booleana con molte variabili di input e di sostituire ogni "vero" con 1 e ogni "falso" con 0:

Se la funzione booleana ha un'elevata complessità del circuito, quel lungo elenco di output sarà in linea di principio indistinguibile da una stringa veramente casuale di 0 e 1, ottenuta lanciando ripetutamente una moneta, per esempio. Ma se la funzione ha una bassa complessità circuitale, la stringa deve avere una descrizione semplice e succinta anche se sembra complicata. Ciò lo rende molto simile alle stringhe pseudocasuali usate in crittografia, la cui breve descrizione è il messaggio segreto sepolto in quell'apparente casualità.

Quindi il risultato di Razborov e Rudich ha mostrato che qualsiasi prova naturale di P ≠ NP produrrebbe anche un algoritmo veloce in grado di distinguere le stringhe pseudocasuali contenenti messaggi nascosti da quelle veramente casuali. La crittografia sicura sarebbe impossibile, esattamente l'opposto di ciò che i ricercatori speravano di stabilire dimostrando P ≠ NP.

D'altra parte, se la crittografia sicura è possibile, le prove naturali non sono una strategia praticabile per dimostrare P ≠ NP, un prerequisito per la crittografia sicura. Questa è la barriera delle prove naturali in poche parole. Sembrava che i teorici della complessità stessero per ricevere uno scherzo crudele.

"Se credi nella durezza, allora dovresti credere che sia difficile dimostrare la durezza", ha detto Kabanets.

Nel Metaverso

Quella connessione tra le implicazioni della congettura P ≠ NP e la difficoltà di dimostrarla era intrigante, ma difficile da definire. Per prima cosa, la barriera delle dimostrazioni naturali bloccava solo un approccio alla dimostrazione di P ≠ NP. Dall'altro, collegava la difficoltà di dimostrare P ≠ NP non a P ≠ NP stesso, ma all'esistenza di una crittografia sicura, un problema strettamente correlato ma non del tutto equivalente. Per comprendere veramente la connessione, i ricercatori dovrebbero abituarsi alla meta-complessità.

"C'è questa intuizione che 'oh, perché P ≠ NP, è difficile dimostrare che P ≠ NP'", ha detto Williams. "Ma per dare un senso a questa intuizione, devi iniziare a pensare al compito di dimostrare qualcosa come P ≠ NP come un problema computazionale."

Questo è quello che ha fatto Kabanets da studente laureato. Era cresciuto in Ucraina e aveva terminato gli studi universitari in informatica due anni dopo la caduta dell'Unione Sovietica. Nel tumulto che seguì, ebbe poche opportunità di approfondire gli argomenti teorici che lo interessavano di più.

"Volevo fare qualcosa di più accademico", ha ricordato Kabanets. "Ed ero anche curioso di vedere il mondo." Si è trasferito in Canada per la scuola di specializzazione, ed è lì che ha imparato a conoscere la barriera delle prove naturali. Come Carmosino, Kabanets è stato colpito dal risultato. "Sembrava molto profondo che tu avessi questa connessione", ha detto.

Nel 2000, verso la fine del suo periodo di specializzazione, ha scoperto che la barriera delle prove naturali continuava a emergere nelle sue conversazioni con Jin-Yi Cai, un teorico della complessità che all'epoca era in visita a Toronto in un anno sabbatico. Cominciarono a vedere la barriera non come un posto di blocco ma come un invito, un'opportunità per indagare con precisione su quanto fosse difficile dimostrare la difficoltà dei problemi. IL carta in cui hanno esposto questa nuova prospettiva sarebbe diventato uno dei primi lavori più influenti nel nascente campo della meta-complessità.

L'articolo di Kabanets e Cai ha evidenziato un problema computazionale implicito nella formulazione di Razborov e Rudich della barriera delle prove naturali: data la tavola di verità di una funzione booleana, determinare se ha una complessità del circuito alta o bassa. Hanno soprannominato questo il problema della dimensione minima del circuito, o MCSP.

MCSP è un problema di meta-complessità per eccellenza: un problema computazionale il cui argomento non è la teoria dei grafi o un altro argomento esterno, ma la stessa teoria della complessità. In effetti, è come una versione quantitativa della domanda che ha spinto i teorici della complessità ad affrontare P contro NP usando l'approccio della complessità del circuito negli anni '1980: quali funzioni booleane sono difficili da calcolare e quali sono facili?

"Se arrivassimo con un algoritmo MCSP, sarebbe come un modo per automatizzare ciò che stiamo facendo nella teoria della complessità", ha detto Impagliazzo. "Dovrebbe almeno darci una visione straordinaria di come svolgere meglio il nostro lavoro".

I teorici della complessità non si preoccupano che questo algoritmo magico li metta senza lavoro: non pensano affatto che esista, perché Razborov e Rudich hanno dimostrato che qualsiasi algoritmo di questo tipo per distinguere le tabelle di verità ad alta complessità da quelle a bassa complessità renderebbe la crittografia impossibile. Ciò significa che MCSP è probabilmente un problema computazionale difficile. Ma quanto è difficile? È NP-completo, come il problema del percorso hamiltoniano e quasi tutti gli altri problemi con cui i ricercatori hanno lottato negli anni '1960?

Per i problemi in NP, "quanto è difficile?" di solito è abbastanza facile rispondere, ma MCSP sembrava essere uno strano valore anomalo. "Abbiamo pochissimi problemi 'fluttuanti' che non sono stati collegati a quest'isola di problemi NP-completi, anche se sembrano essere difficili", ha detto Kabanets.

Kabanets sapeva che lui e Cai non erano i primi a prendere in considerazione il problema che avevano soprannominato MCSP. I matematici sovietici avevano studiato un problema molto simile a partire dagli anni '1950, in un primo tentativo di comprendere la difficoltà intrinseca di diversi problemi computazionali. Leonid Levin aveva lottato con esso mentre sviluppava quella che sarebbe diventata la teoria della NP-completezza alla fine degli anni '1960, ma non poteva dimostrarlo NP-completo e pubblicò il suo articolo seminale senza di esso.

Successivamente, il problema ha attirato poca attenzione per 30 anni, fino a quando Kabanets e Cai non hanno notato la sua connessione con la barriera delle prove naturali. Kabanets non si aspettava di risolvere la questione da solo, invece voleva esplorare il motivo per cui era stato così difficile dimostrare che questo problema apparentemente difficile sulla durezza computazionale era in realtà difficile.

"È, in un certo senso, meta-meta-complessità", ha detto Rahul Santhanam, un teorico della complessità all'Università di Oxford.

Ma era la durezza fino in fondo, o c'era almeno un modo per capire perché i ricercatori non erano riusciti a dimostrare che MCSP era NP-completo? Kabanets ha scoperto che, sì, c'era una ragione: la difficoltà di comprendere la complessità del circuito funge da barriera a qualsiasi strategia nota per dimostrare la completezza NP di MCSP, un problema che riguarda di per sé la difficoltà di comprendere la complessità del circuito. La logica contorta e controproducente della barriera delle prove naturali sembrava inevitabile.

È anche possibile che MCSP non sia NP-completo, ma anche questo sembra improbabile: alcune varianti più semplici del problema sono già note per essere NP-complete.

"Semplicemente non abbiamo un bel posto dove metterlo che lo colleghi direttamente a tutti gli altri problemi che studiamo", ha detto Impagliazzo.

Kabanets aveva illuminato lo strano comportamento di MCSP, ma non sapeva come fare ulteriori progressi. La ricerca sulla meta-complessità si è ridotta a un rivolo. Sarebbe rifiorito 16 anni dopo, quando i ricercatori hanno scoperto una connessione sorprendente con un'altra domanda fondamentale: quanto è difficile risolvere i problemi se ti interessa solo ottenere la risposta giusta il più delle volte?

La guerra dei mondi

Per i problemi quotidiani, le risposte che funzionano la maggior parte delle volte sono spesso abbastanza buone. Pianifichiamo i nostri spostamenti per modelli di traffico tipici, ad esempio, non per gli scenari peggiori.

La maggior parte dei teorici della complessità è più difficile da soddisfare: si accontentano di dichiarare un problema facile solo se riescono a trovare un algoritmo veloce che ottiene la risposta giusta su ogni possibile input. Questo approccio standard classifica i problemi in base a ciò che i ricercatori chiamano complessità del "caso peggiore". Ma c'è anche una teoria della complessità del "caso medio", in cui i problemi sono considerati facili se c'è un algoritmo veloce che ottiene la risposta giusta sulla maggior parte degli input.

La distinzione è importante per i crittografi. Immagina un problema computazionale facile da risolvere per quasi tutti gli input, ad eccezione di alcuni casi ostinati in cui il miglior algoritmo fallisce. La teoria della complessità del caso peggiore lo considera un problema difficile, ma per la crittografia è inutile: se solo alcuni dei tuoi messaggi sono difficili da decifrare, qual è il punto?

In realtà è stato Levin che ha avviato lo studio rigoroso della complessità del caso medio, un decennio dopo il suo lavoro pionieristico sulla NP-completezza. Negli anni successivi, si era scontrato con le autorità sovietiche: era un piantagrane irriverente che occasionalmente minava le attività patriottiche nel suo gruppo giovanile del Partito Comunista. Nel 1972 gli fu negato il dottorato per ragioni esplicitamente politiche.

"Per avere successo in Unione Sovietica come giovane ricercatore, non puoi essere molto supponente, ed è difficile immaginare che Leonid non sia supponente", ha detto Impagliazzo.

Levin è emigrato negli Stati Uniti nel 1978 ea metà degli anni '1980 ha rivolto la sua attenzione alla complessità del caso medio. Iniziò a lavorare con altri per sviluppare ulteriormente la teoria, incluso Impagliazzo, all'epoca uno studente laureato. Ma anche mentre facevano progressi, Impagliazzo ha scoperto che i ricercatori spesso parlavano tra loro. Voleva mettere tutti sulla stessa pagina, e non ha aiutato il fatto che i documenti di Levin fossero notoriamente succinti - quello che avviato il campo di complessità media era lungo meno di due pagine.

"Stavo per fare una traduzione del lavoro di Leonid in termini tecnici più accessibili", ha detto Impagliazzo. Ha deciso di iniziare con una breve panoramica giocosa del quadro generale prima di tuffarsi nella matematica. "Quel tipo ha preso il sopravvento sul giornale, ed è l'unica parte che qualcuno ricorda comunque."

Il carta, pubblicato nel 1995, è diventato subito un classico. Impagliazzo ha coniato nomi stravaganti per cinque mondi distinti da diversi gradi di durezza computazionale e diverse capacità crittografiche. Viviamo in uno di questi mondi, ma non sappiamo quale.

Da quando è apparso l'articolo di Impagliazzo, i ricercatori hanno sognato di eliminare parti del suo multiverso in miniatura, restringendo lo spazio delle possibilità dimostrando che dopo tutto alcuni dei mondi non sono possibili. Due mondi sono bersagli particolarmente allettanti: quelli in cui la crittografia è impossibile anche se P ≠ NP.

In uno di questi mondi, chiamato Heuristica, tutti i problemi NP-completi sono facili da risolvere sulla maggior parte degli input, ma gli algoritmi veloci occasionalmente commettono errori, quindi questi problemi sono ancora considerati difficili dagli standard della teoria della complessità del caso peggiore. Questo è il mondo in cui la crittografia è impossibile perché quasi ogni codice è facilmente decifrabile. Nell'altro mondo, chiamato Pessiland, la crittografia è impossibile per un motivo diverso: ogni problema è difficile nel senso medio, ma la crittografia di un messaggio lo rende illeggibile anche per il destinatario previsto.

Questi due mondi risultano essere strettamente legati ai problemi di meta-complessità - in particolare, il destino di Heuristica è legato all'annosa questione se MCSP sia NP-completo. La domanda che ha affascinato Kabanets e sconcertato Levin tanto tempo fa non è una mera curiosità: c'è un intero mondo in gioco.

Per escludere Heuristica, i ricercatori dovrebbero abbattere la distinzione tra complessità del caso peggiore e caso medio, ovvero dovrebbero dimostrare che qualsiasi algoritmo ipotetico che risolva correttamente un problema NP-completo sulla maggior parte degli input può effettivamente risolverlo in tutti i casi. È noto che questo tipo di connessione, chiamata riduzione dal caso peggiore al caso medio, esiste per alcuni problemi, ma nessuno di essi è NP-completo, quindi quei risultati non implicano nulla di più generale. L'eliminazione di Heuristica porterebbe i crittografi a metà strada per realizzare il sogno di una crittografia sicura basata sull'unico presupposto che P ≠ NP.

Ma distruggere un mondo non è un'impresa da poco. Nel 2003, due teorici della complessità ha mostrato che gli approcci esistenti per dimostrare le riduzioni dal caso peggiore al caso medio per problemi noti NP-completi implicherebbero conseguenze stravaganti, suggerendo che tali prove probabilmente non sono possibili.

I ricercatori dovrebbero trovare un altro approccio e ora pensano che MCSP potrebbe essere proprio il problema di cui hanno bisogno. Ma questo non sarebbe diventato chiaro per oltre un decennio. Il primo barlume della connessione è emerso dal persistente fascino di Marco Carmosino per la barriera delle prove naturali.

Carmosino ha incontrato per la prima volta la ricerca sulla meta-complessità come studente laureato attraverso a carta 2013 di Kabanets e altri quattro ricercatori, che svilupparono ulteriormente l'approccio alla barriera delle prove naturali che Kabanets aveva aperto la strada più di un decennio prima. Ha solo rafforzato la sua convinzione che ci fosse ancora altro da imparare dal classico articolo di Razborov e Rudich.

"All'epoca ero ossessionato da quel giornale", ha detto Carmosino. "Niente è cambiato."

L'ossessione ha finalmente dato i suoi frutti durante una visita a un seminario semestrale presso l'Università della California, Berkeley, dove ha trascorso la maggior parte del suo tempo a parlare con Impagliazzo, Kabanets e Antonina Kolokolova, un teorico della complessità della Memorial University of Newfoundland che aveva collaborato con Kabanets all'articolo del 2013. Carmosino aveva già lavorato con loro tre una volta, e quella proficua collaborazione gli diede la fiducia necessaria per tempestarli di domande sull'argomento che lo affascinava di più.

"Stava infastidendo le persone in modo positivo", ha ricordato Kabanets.

All'inizio, Carmosino aveva nuove idee per dimostrare la NP-completezza per la versione di MCSP che era apparsa nell'articolo di Razborov e Rudich sulla barriera delle dimostrazioni naturali. Ma quelle idee non hanno avuto successo. Invece, un'osservazione improvvisata di Impagliazzo ha fatto capire ai quattro ricercatori che la barriera delle prove naturali poteva produrre algoritmi più potenti di quanto chiunque avesse realizzato: c'era una mappa segreta incisa nel posto di blocco.

In un carta 2016, i quattro ricercatori hanno dimostrato che un certo tipo di algoritmo MCSP del caso medio potrebbe essere utilizzato per costruire un algoritmo del caso peggiore per identificare schemi nascosti in stringhe di cifre dall'aspetto casuale, un compito che gli scienziati informatici chiamano "apprendimento". È un risultato sorprendente perché l'apprendimento intuitivo sembra più difficile del compito di classificazione binaria - alta complessità o bassa complessità - eseguita da un algoritmo MCSP. E, sorprendentemente, ha collegato la complessità del caso peggiore di un compito alla complessità del caso medio dell'altro.

"Non era affatto ovvio che esistesse una tale connessione", ha detto Impagliazzo.

Un algoritmo veloce per MCSP è puramente ipotetico per i circuiti booleani generali: non può esistere a meno che MCSP non si riveli un facile problema computazionale, nonostante tutte le prove del contrario, e ciò significa che l'algoritmo di apprendimento implicito nell'articolo dei quattro ricercatori è altrettanto ipotetico.

Ma per alcune versioni più semplici di MCSP - che distinguono le tabelle di verità ad alta complessità da quelle a bassa complessità quando ci sono restrizioni specifiche sui circuiti - gli algoritmi veloci sono noti da molti anni. L'articolo di Carmosino, Impagliazzo, Kabanets e Kolokolova ha dimostrato che questi algoritmi potevano essere trasformati in algoritmi di apprendimento anch'essi limitati ma ancora più potenti di quelli che i ricercatori avevano precedentemente compreso a un livello teorico così rigoroso.

"In qualche modo il loro sapore autoreferenziale ti permette di fare cose che apparentemente non puoi fare con problemi più standard", ha detto Ilango.

Il risultato ha catturato l'attenzione dei teorici della complessità che lavorano su altri argomenti. Era anche un'anteprima di ulteriori connessioni tra meta-complessità e complessità del caso medio che sarebbero emerse negli anni a venire.

Soprattutto, è stata una testimonianza di quanto lontano possono arrivare i ricercatori ponendo semplici domande sugli ostacoli che a prima vista sembrano solo ostacolare il loro progresso.

"Questo tipo di dualità è un tema che attraversa almeno gli ultimi 30 o 40 anni di complessità", ha detto Impagliazzo. "Gli ostacoli sono spesso le opportunità."

Credito parziale

Il progresso è solo accelerato negli anni da quando Carmosino e i suoi colleghi hanno pubblicato il loro articolo.

"Stanno accadendo nuove cose", ha detto Kolokolova. "Ci sono molti giovani ricercatori davvero, davvero brillanti".

Ilango è uno di questi giovani ricercatori: nei suoi primi tre anni di scuola di specializzazione, ha affrontato l'arduo problema aperto di dimostrare MCSP NP-completo utilizzando una strategia su due fronti: dimostrare la NP-completezza per semplice versioni di MCSP, come hanno fatto i ricercatori sulla complessità dei circuiti quando hanno attaccato P contro NP negli anni '1980, dimostrando anche la completezza NP per versioni più complicate, che intuitivamente sembrano più difficili e quindi sono forse più facili da dimostrare difficili.

Ilango attribuisce il suo interesse per la meta-complessità a Eric Allender, un teorico della complessità alla Rutgers University e uno dei pochi ricercatori che hanno continuato a lavorare sulla meta-complessità negli anni 2000 e nei primi anni 2010. "Il suo entusiasmo era contagioso", ha detto Ilango.

Un altro giovane ricercatore ispirato da Allender lo è Shuichi Hirahara, ora professore all'Istituto Nazionale di Informatica di Tokyo. Mentre era ancora uno studente laureato nel 2018, Hirahara ha rivelato la vera portata della relazione tra meta-complessità e complessità del caso medio che Carmosino e i suoi coautori avevano scoperto. Quei quattro ricercatori avevano trovato una connessione tra la complessità del caso medio di un problema - MCSP - e la complessità del caso peggiore di un altro - l'apprendimento booleano. Hirahara ha sviluppato ulteriormente le loro tecniche derivare una riduzione dal caso peggiore al caso medio per MCSP. Il suo risultato implica che un ipotetico algoritmo MCSP di caso medio come quello che Carmosino ei suoi colleghi avevano considerato sarebbe effettivamente abbastanza potente da risolvere una versione leggermente diversa di MCSP senza commettere errori.

Il risultato di Hirahara è entusiasmante perché molti ricercatori sospettano che MCSP sia NP-completo, a differenza di tutti gli altri problemi per i quali sono note riduzioni dal caso peggiore al caso medio. Se possono estendere i risultati di Hirahara per coprire tutti gli algoritmi del caso medio e quindi dimostrare che MCSP è NP-completo, ciò dimostrerebbe che non viviamo in Heuristica.

"Sarebbe davvero un risultato sconvolgente", ha detto Santhanam.

Dimostrare che MCSP è NP-completo può sembrare un compito arduo, dopotutto la questione è aperta da oltre 50 anni. Ma dopo un sfondamento l'anno scorso da Hirahara, i ricercatori sono ora molto più vicini di quanto ci si sarebbe aspettati qualche anno fa.

Hirahara ha dimostrato la completezza NP per una variante del problema chiamata MCSP parziale, in cui si ignorano determinate voci in ciascuna tabella di verità. La sua dimostrazione si basava su metodi sviluppati da Ilango per dimostrare che l'MCSP parziale era equivalente a un problema apparentemente non correlato che coinvolgeva una tecnica crittografica chiamata condivisione segreta. Questo è un modo per dividere un messaggio crittografato tra molte persone in modo che possa essere decodificato solo se una certa frazione di esse lavora insieme.

Per qualsiasi applicazione reale in crittografia, vorresti conoscere quella frazione in anticipo, ma con l'aiuto di trucchi crittografici extra, puoi costruire uno scenario frustrante in cui è difficile solo capire quante persone devono cooperare. Hirahara ha trovato un modo per dimostrare che questo problema crittografico artificioso era NP-completo e poi ha dimostrato che la prova implicava anche la completezza NP dell'MCSP parziale.

Questo risultato ha stimolato i ricercatori nella meta-complessità anche più del lavoro precedente di Hirahara, e anche altri ricercatori se ne sono accorti: il teorico della complessità e blogger Lance Fortnow l'ha soprannominato il risultato dell'anno. Questo perché affrontare tali versioni di "funzioni parziali" di problemi computazionali è stato un passo intermedio chiave in altre dimostrazioni di NP-completezza.

"È un lavoro straordinario", ha detto Williams. "Tutti pensavano che questi problemi parziali fossero più o meno la stessa difficoltà del problema completo".

Rimangono ostacoli alla dimostrazione della completezza NP per la versione completa di MCSP. Ma nessuno è il tipo di barriera che suggerisce la necessità di un toolkit completamente nuovo: potrebbe essere solo questione di trovare il modo giusto per combinare tecniche note. Una dimostrazione stabilirebbe finalmente lo status di uno dei pochi problemi che hanno resistito alla classificazione da quando esiste la teoria della complessità. Tramite e-mail, Levin ha scritto: "Mi umilierebbe mostrando che sono stato stupido per non essere stato in grado di vederlo :-)."

I pezzi mancanti

MCSP non è nemmeno l'unico problema di meta-complessità che ha stimolato un importante passo avanti. Nel 2020, il crittografo Cornell Tech Passo Rafael e il suo studente laureato Yanyi Liu scoperto un collegamento tra un diverso problema di meta-complessità e un protocollo crittografico fondamentale che definisce il confine tra Heuristica e Pessiland, il peggiore dei mondi di Impagliazzo (dove i problemi NP-completi sono difficili nel senso del caso medio ma la crittografia è ancora impossibile). Ciò rende il problema che hanno studiato un ottimo candidato per un assalto a Pessiland, e il loro lavoro più recente indica che potrebbe funzionare anche contro Heuristica.

"Mancano diversi pezzi del puzzle", ha detto Pass. "Per me è semplicemente magico che questi campi siano così intimamente connessi."

Hirahara avverte che le sfide attendono ancora i ricercatori intenti a selezionare i mondi che Impagliazzo ha evocato 30 anni fa. "Vorrei dire che a un certo punto Heuristica e Pessiland saranno esclusi, ma non sono sicuro di quanto siamo vicini", ha detto.

Molti ricercatori si aspettano che la difficoltà maggiore sarà colmare un divario apparentemente innocuo tra due diversi modelli di complessità del caso medio. I crittografi di solito studiano algoritmi di caso medio che commettono errori in entrambe le direzioni, etichettando occasionalmente stringhe casuali come pseudocasuali e viceversa. Le riduzioni di Hirahara dal caso peggiore al caso medio, nel frattempo, funzionano per gli algoritmi del caso medio che fanno solo il primo tipo di errore. Sottili distinzioni come questa possono fare un'enorme differenza nella teoria della complessità. Ma nonostante questo ostacolo e molti altri, Allender non può fare a meno di emettere una nota di cauto ottimismo.

"Cerco di non lasciarmi credere troppo perché c'è una storia piuttosto consolidata di niente che funziona", ha detto. "Ma stiamo assistendo a molti sviluppi davvero entusiasmanti: modi per superare cose che sembravano barriere".

Se c'è una lezione che i ricercatori hanno imparato dalle loro lotte per rispondere alla domanda P contro NP - o anche solo capirla - è che la teoria della complessità è essa stessa complessa. Ma quella sfida è proprio ciò che rende la ricerca così gratificante.

"In realtà è fantastico che sia così difficile", ha detto Carmosino. "Non mi annoierò mai."

Nota del redattore: Scott Aaronson è un membro di Quanta Magazine'S Comitato consultivo.