Kompleksitetsteoriens 50-årige reise til kunnskapens grenser | Quanta Magazine

I den første uken av høstsemesteret i 2007 dro Marco Carmosino seg til en mattetime som kreves for alle hovedfag i informatikk ved University of Massachusetts, Amherst. Carmosino, en sophomore, vurderte å droppe ut av college for å designe videospill. Så stilte professoren et enkelt spørsmål som ville forandre livet hans: Hvordan vet du at matematikk faktisk fungerer?

"Det fikk meg til å sette meg opp og være oppmerksom," husket Carmosino, nå teoretisk informatiker ved IBM. Han meldte seg på et valgfritt seminar om arbeidet til Kurt Gödel, hvis svimlende selvrefererende argumenter først avslørte grensene for matematisk resonnement og skapte grunnlaget for alt fremtidig arbeid med de grunnleggende grensene for beregning. Det var mye å ta inn over seg.

"Jeg forsto 100% ikke," sa Carmosino. – Men jeg visste at jeg ville.

I dag finner selv erfarne forskere forståelse en mangelvare når de konfronterer det sentrale åpne spørsmålet i teoretisk informatikk, kjent som P versus NP-problemet. I hovedsak spør det spørsmålet om mange beregningsproblemer som lenge har vært ansett som ekstremt vanskelige, faktisk kan løses enkelt (via en hemmelig snarvei vi ikke har oppdaget ennå), eller om de, som de fleste forskere mistenker, virkelig er vanskelige. På spill er intet mindre enn hva som er kjent.

Til tross for flere tiår med innsats fra forskere innen beregningskompleksitetsteori - studiet av slike spørsmål om den iboende vanskeligheten til forskjellige problemer - har en løsning på P versus NP-spørsmålet forblitt unnvikende. Og det er ikke engang klart hvor et mulig bevis skal begynne.

"Det er ikke noe veikart," sa Michael Sipser, en veteran kompleksitetsteoretiker ved Massachusetts Institute of Technology som brukte år på å kjempe med problemet på 1980-tallet. "Det er som om du skal ut i villmarken."

Det ser ut til at det er en vanskelig oppgave å bevise at beregningsproblemer er vanskelig å løse. Men hvorfor er det så vanskelig? Og hvor vanskelig er det egentlig? Carmosino og andre forskere innen underfeltet metakompleksitet omformulerer spørsmål som dette som beregningsproblemer, og driver feltet fremover ved å snu linsen til kompleksitetsteori tilbake på seg selv.

"Du tenker kanskje," OK, det er litt kult. Kanskje kompleksitetsteoretikerne har blitt gale," sa Rahul Ilango, en doktorgradsstudent ved MIT som har produsert noen av de mest spennende nylige resultatene på feltet.

Ved å studere disse innovervendte spørsmålene har forskere lært at hardheten ved å bevise beregningshardhet er nært knyttet til grunnleggende spørsmål som til å begynne med kan virke urelaterte. Hvor vanskelig er det å oppdage skjulte mønstre i tilsynelatende tilfeldige data? Og hvis virkelig vanskelige problemer eksisterer, hvor ofte er de vanskelige?

"Det har blitt klart at meta-kompleksitet er nært til hjertet av ting," sa Scott Aaronson, en kompleksitetsteoretiker ved University of Texas, Austin.

Dette er historien om den lange og svingete stien som førte forskere fra P versus NP-problematikken til metakompleksitet. Det har ikke vært en lett reise - stien er full av falske svinger og veisperringer, og den går tilbake på seg selv igjen og igjen. Men for metakompleksitetsforskere er denne reisen inn i et ukjent landskap sin egen belønning. Begynn å stille tilsynelatende enkle spørsmål, sa Valentine Kabanets, en kompleksitetsteoretiker ved Simon Fraser University i Canada, og "du aner ikke hvor du skal dra."

Kjente ukjente

P versus NP-problemet skylder sitt mangelfulle navn til kompleksitetsteoretikeres vane med å sortere beregningsproblemer i brede "kompleksitetsklasser” med etiketter som antyder Nasdaq ticker-symboler. Et beregningsproblem er et som i prinsippet kan løses med en algoritme - en presist spesifisert liste med instruksjoner. Men ikke alle algoritmer er like nyttige, og variasjonen mellom algoritmer antyder grunnleggende forskjeller mellom problemer i ulike klasser. Utfordringen for kompleksitetsteoretikere er å gjøre disse hintene til strenge teoremer om forholdet mellom kompleksitetsklasser.

Disse relasjonene gjenspeiler uforanderlige sannheter om beregning som går langt utover noen spesifikk teknologi. "Dette er som å oppdage universets lover," sa Kabanets.

"P" og "NP" er de to mest kjente medlemmene av en voksende menasjeri av hundrevis av kompleksitetsklasser. Grovt sett er P klassen av problemer som enkelt kan løses, som å alfabetisere en liste. NP er klassen av problemer med lett kontrollerbare løsninger, som sudoku-oppgaver. Siden alle lett løselige oppgaver også er lette å sjekke, er oppgaver i P også i NP. Men noen NP-problemer virker vanskelige å løse - du kan ikke umiddelbart intuere løsningen på et sudoku-puslespill uten først å prøve ut mange muligheter. Kan det være at denne tilsynelatende hardheten bare er en illusjon - at det finnes ett enkelt triks for å løse alle enkelt kontrollerbare problemer?

I så fall er P = NP: De to klassene er likeverdige. Hvis det er tilfelle, må det være en eller annen algoritme som gjør det trivielt å løse enorme sudoku-gåter, optimalisere globale fraktruter, bryte toppmoderne kryptering og automatisere bevisene til matematiske teoremer. Hvis P ≠ NP, vil mange beregningsproblemer som i prinsippet kan løses i praksis for alltid forbli utenfor vår rekkevidde.

Forskere bekymret seg for grensene for formell matematisk resonnement lenge før P versus NP-problemet først ble artikulert - ja, lenge før begynnelsen av moderne informatikk. I 1921, mens han strevde med det samme spørsmålet som ville fange Carmosinos oppmerksomhet nesten et århundre senere, foreslo matematikeren David Hilbert et forskningsprogram for å forankre matematikk i absolutt sikkerhet. Han håpet å ta utgangspunkt i noen få enkle antagelser, kalt aksiomer, og utlede en enhetlig matematisk teori som møtte tre nøkkelkriterier.

Hilberts første betingelse, konsistens, var det essensielle kravet om at matematikk skulle være fri for motsetninger: Hvis to motstridende utsagn kunne bevises med utgangspunkt i de samme aksiomer, ville hele teorien være uunngåelig. Men en teori kan være fri for selvmotsigelser og fortsatt begrenset i sin rekkevidde. Det var motivasjonen for Hilberts andre betingelse, fullstendighet: kravet om at alle matematiske utsagn enten skal være beviselig sanne eller beviselig usanne. Hans tredje kriterium, avgjørbarhet, krevde en utvetydig mekanisk prosedyre for å avgjøre om et matematisk utsagn var sant eller usant. På en konferanse i 1930 erklærte Hilbert: «Vårt slagord skal være 'Vi må vite, vi vil vite.'»

Bare et år senere ga Gödel det første slaget mot Hilberts drøm. Han beviste at et selvødeleggende utsagn som "denne påstanden er ubeviselig" kan avledes fra et hvilket som helst passende sett med aksiomer. Hvis et slikt utsagn faktisk ikke kan bevises, er teorien ufullstendig, men hvis den er bevisbar, er teorien inkonsekvent - et enda verre resultat. I det samme papiret beviste Gödel også at ingen matematisk teori noen gang kunne bevise sin egen konsistens.

Forskere hadde fortsatt håp om at en fremtidig teori om matematikk, selv om den nødvendigvis er ufullstendig, likevel kan bevises avgjørbar. Kanskje de kunne utvikle prosedyrer som vil identifisere alle bevisbare utsagn mens de unngår irriterende påstander som Gödels. Problemet var at ingen visste hvordan de skulle resonnere om disse hypotetiske prosedyrene.

Så i 1936 omformulerte en 23 år gammel doktorgradsstudent ved navn Alan Turing Hilberts avgjørbarhetstilstand på det da ukjente regnespråket og ga det et fatalt slag. Turing formulerte en matematisk modell - nå kjent som Turing maskin — som kunne representere alle mulige algoritmer, og viste at hvis Hilberts prosedyre eksisterte, ville den passet inn i denne modellen. Han brukte deretter selvrefererende metoder som Gödels til bevise eksistensen av utsagn som ikke kan avgjøres - eller, tilsvarende, uberegnelige problemer som ingen algoritme kunne løse.

Hilberts program lå i ruiner: Det ville for alltid være grunnleggende grenser for hva som kunne bevises og hva som kunne beregnes. Men etter hvert som datamaskiner utviklet seg fra teoretiske abstraksjoner til virkelige maskiner, innså forskerne at Turings enkle skille mellom løsbare og uløselige problemer etterlot mange spørsmål ubesvart.

På 1960-tallet hadde informatikere utviklet raske algoritmer for å løse noen problemer, mens for andre var de eneste kjente algoritmene uutholdelig trege. Hva om spørsmålet ikke bare var om problemer er løsbare, men hvor vanskelige de er å løse?

"En rik teori dukker opp, og vi vet ikke svarene lenger," sa Carmosino.

Divergente stier

For å illustrere hvor forvirrende spørsmål om hardhet kan være, la oss vurdere et par nært beslektede problemer som involverer grafer. Dette er nettverk av punkter, kalt noder, forbundet med linjer, kalt kanter. Dataforskere bruker dem til å modellere alt fra kvanteberegning til flyt av trafikk.

Anta at du får en graf og bedt om å finne noe som kalles en Hamiltonsk bane - en rute som går gjennom hver node nøyaktig én gang. Dette problemet er klart løses i prinsippet: Det er bare et begrenset antall mulige veier, så hvis alt annet feiler kan du bare sjekke hver enkelt. Det er greit hvis det bare er noen få noder, men for enda litt større grafer kommer antallet muligheter ut av kontroll, noe som raskt gjør denne enkle algoritmen ubrukelig.

Det er mer sofistikerte Hamiltonske banealgoritmer som gir en bedre kamp, ​​men tiden som algoritmer krever for å løse problemet, vokser alltid eksponentielt med størrelsen på grafen. Grafer trenger ikke å være veldig store før selv de beste algoritmeforskerne har oppdaget ikke kan finne en vei "i rimelig tid," sa Russell Impagliazzo, en kompleksitetsteoretiker ved University of California, San Diego. "Og med 'rimelig lang tid' mener jeg 'før universet tar slutt'."

Hamilton-stiproblemet har en annen interessant egenskap. Hvis noen hevder å ha funnet en Hamiltonsk bane på en bestemt graf, kan du raskt sjekke om løsningen er gyldig, selv om grafen er veldig stor. Alt du trenger å gjøre er å følge stien og krysse av nodene én etter én, og sjekke for å være sikker på at du ikke har krysset av noen node to ganger. Hvis ingen noder mangler på slutten, er banen Hamiltonsk.

Tiden som kreves for å kjøre denne løsningssjekkingsalgoritmen er proporsjonal med størrelsen på grafen. Det setter den inn i den bredere kategorien av polynomiske algoritmer, hvis kjøretider øker som polynomfunksjoner av grafstørrelsen. Polynomvekst er tam sammenlignet med eksponentiell vekst, så polynomiske algoritmer forblir levedyktige selv på store grafer. "Det er dramatisk mer effektivt," sa Carmosino.

Det Hamiltonske baneproblemet har en sterk asymmetri: Du kan bekrefte en riktig løsning ved å bruke en rask polynomalgoritme, men for å finne en løsning trenger du en langsom eksponentiell algoritme. Den asymmetrien virker kanskje ikke overraskende - det er lettere å gjenkjenne et kunstnerisk mesterverk enn å lage et, lettere å sjekke et matematisk bevis enn å bevise et nytt teorem - men ikke alle beregningsproblemer har denne asymmetriske karakteren. Faktisk oppfører et problem som ligner veldig på å finne Hamilton-stier seg ganske annerledes.

Anta at du igjen får en graf, men nå blir du bedt om å finne en "eulerisk bane" som krysser hver kant nøyaktig én gang. Igjen, det er en polynomalgoritme for å sjekke mulige løsninger, men denne gangen er det også en polynomalgoritme for å løse problemet. Ingen asymmetri her. I kompleksitetsteori virker noen veier lettere å finne enn andre.

Både det Hamiltonske baneproblemet og det Euleriske baneproblemet er i kompleksitetsklassen NP, definert til å inkludere alle problemer hvis løsninger kan kontrolleres av polynomiske algoritmer. Det euleriske baneproblemet faller også inn i klassen P fordi en polynomisk algoritme kan løse det, men tilsynelatende er det ikke sant for det Hamiltonske baneproblemet. Hvorfor skulle disse to grafoppgavene, så overfladisk like, skille seg så dramatisk fra hverandre? Det er essensen av P versus NP-problemet.

Universelt vanskelig

Til å begynne med virket kompleksitetsklasser som praktiske kategorier for å sortere problemer som var like, men ikke direkte relaterte - ingen mistenkte at det å finne Hamiltonske stier hadde noe å gjøre med andre vanskelige beregningsproblemer.

Så i 1971, innen et år etter å ha flyttet til University of Toronto etter å ha blitt nektet ansettelse i USA, kom kompleksitetsteoretikeren Stephen Cook publisert en ekstraordinært resultat. Han identifiserte et spesielt NP-problem med en merkelig funksjon: Hvis det er en polynomalgoritme som kan løse det problemet, kan den også løse alle andre problemer i NP. Cooks "universelle" problem, så det ut til, var en ensom kolonne som støttet opp klassen av tilsynelatende vanskelige problemer, og skilte dem fra de enkle problemene nedenfor. Knekk det ene problemet, og resten av NP vil rase sammen.

Cook mistenkte at det ikke fantes noen rask algoritme for hans universelle problem, og han sa så mye midtveis i avisen, og la til: "Jeg føler at det er verdt å bruke betydelig innsats på å prøve å bevise denne formodningen." "Betraktelig innsats" ville vise seg å være en underdrivelse.

Omtrent på samme tid oppkalte en doktorgradsstudent i Sovjetunionen Leonid Levin bevist en lignende resultat, bortsett fra at han identifiserte flere forskjellige universelle problemer. I tillegg kommer den amerikanske kompleksitetsteoretikeren Richard Karp beviste at universalitetsegenskapen identifisert av Cook (og Levin, selv om Karp og Cook ikke kjente til Levins arbeid før år senere) var i seg selv alt annet enn universell. Nesten hvert NP-problem uten en kjent polynomalgoritme - det vil si nesten alle enkelt kontrollerbare problemer som virket vanskelige - hadde samme egenskap, som ble kjent som NP-fullstendighet.

Dette betyr alle NP-komplette problemer - Hamiltonian-baneproblemet, sudoku og tusener av andre — er i en nøyaktig forstand ekvivalente. "Du har alle disse forskjellige naturlige oppgavene, og de viser seg alle på magisk vis å være den samme oppgaven," sa Ilango. "Og vi vet fortsatt ikke om den samme oppgaven er mulig eller ikke."

Å løse vanskelighetsgraden til ethvert NP-komplett problem ville være nok til å løse P versus NP-spørsmålet. Hvis P ≠ NP, holdes skillet mellom lette og vanskelige problemer oppe av tusenvis av kolonner som alle er like sterke. Hvis P = NP, er hele bygningen på randen av kollaps, og venter bare på at et enkelt stykke skal falle.

Cook, Levin og Karp hadde forent det som virket som mange urelaterte problemer. Nå var alt kompleksitetsteoretikere å gjøre var å løse ett problem: Er P = NP eller ikke?

Femti år senere forblir spørsmålet ubesvart. Kabaneter sammenlignet resonnement om grensene for beregning med å kartlegge et stort territorium uten noen følelse av det store bildet. Et vesen med ubegrenset regnekraft kan kikke ned fra en fjelltopp og ta inn hele landskapet på en gang, men bare dødelige kan ikke regne med den slags fordeler. "De av oss på bunnen av fjellet kan prøve å kanskje hoppe opp og ned for bedre utsikt," sa han.

Anta at P = NP. For å bevise det, må forskere finne en rask algoritme for et NP-komplett problem, som kanskje gjemmer seg i et obskurt hjørne av det enorme landskapet. Det er ingen garanti for at de vil finne det snart: Kompleksitetsteoretikere har av og til oppdaget geniale algoritmer for tilsynelatende vanskelige (men ikke NP-komplette) problemer først etter flere tiår med arbeid.

Anta nå at P ≠ NP. Å bevise det virker enda vanskeligere. Kompleksitetsteoretikere ville måtte fastslå at ingen rask algoritme muligens kunne eksistere, og effektivt forutse og hindre den beste innsatsen til alle fremtidige forskere.

Å ikke vite hvor du skal begynne er en del av problemet. Men det er ikke slik at forskere ikke har prøvd. I løpet av tiårene har de angrepet problemet fra mange vinkler og funnet veien blokkert ved hver sving. "Det er en av de mest åpenbare sannhetene i teoretisk informatikk," sa Carmosino. "Når du har et fenomen som er så holdbart, vil du ha en forklaring."

Ved Carmosinos siste år på college, hadde nysgjerrigheten hans ført ham fra Gödel til et hovedfag i kompleksitetsteori. Han ble overrasket over å innse at han brukte mer tid på lekser enn på lidenskapsprosjektet sitt, et dataprogram som ville lære eventyrenes narrative struktur og generere nye.

"Jeg tenkte, 'Wow, jeg må ta dette seriøst'," husket Carmosino. Kort tid etter ble han så oppslukt av emnet at mentoren hans forsiktig foreslo at han skulle revurdere planene sine etter endt utdanning.

"Han sa: "Du vet, hvis du vil fortsette å gjøre dette, hvis du vil fortsette med teoretisk informatikk og kompleksitetsteori, kan du: Det kalles grad skole," sa Carmosino. Etter å ha tatt sin master, flyttet han til San Diego i 2012 for å jobbe mot en doktorgrad veiledet av Impagliazzo.

Carmosinos hovedmål var til å begynne med å bedre forstå en landemerke papir fra to tiår tidligere som hadde fanget fantasien hans. Den artikkelen, av kompleksitetsteoretikerne Alexander Razborov og Steven Rudich, hadde vist at en viss "naturlig" strategi for å bevise P ≠ NP nesten helt sikkert ville mislykkes, fordi suksess ville komme til en høy pris - den fullstendige sammenbruddet av kryptografi - som forskere anså som svært usannsynlig. Forskere tolket Razborov og Rudichs resultat som en barriere for denne populære tilnærmingen til å bevise P ≠ NP.

Denne "naturlige bevisbarrieren" er bare en av mange kjente barrierer for å løse åpne problemer i kompleksitetsteori. Hver av dem fungerer som en veisperring, og advarer om at en tilsynelatende lovende sti faktisk er en blindvei. Sammen indikerer disse barrierene at ethvert bevis som løser P versus NP-problemet må være radikalt annerledes enn noe som er brukt tidligere; det er derfor de fleste forskere mener at en løsning fortsatt er langt unna. Men i det minste forteller barrierer dem hvor de ikke skal lete.

"Kompleksitetsteori er både forbannet og velsignet med så mange barrierer," sa Ilango.

Da Carmosino møtte den naturlige bevisbarrieren, var den nesten 20 år gammel. Men han mistenkte at det hadde mer lærdom for forskere. Den følelsen ville en dag bli bekreftet når han og tre kolleger viste et overraskende resultat ved å undersøke den naturlige bevisbarrieren fra metakompleksitetens perspektiv. Beviset deres var et av noen få store resultater som utløste en ny interesse for metakompleksitet, noe som førte til en mengde fremgang de siste årene.

Men for å følge sporet fra den naturlige bevisbarrieren til metakompleksitet, må vi hoppe tilbake til der vi forlot forskere på 1970-tallet, da de først begynte å takle P versus NP-problemet. Hva gjorde det så vanskelig å bevise problemer vanskelig?

En kretsvei

Først prøvde forskere å bevise P ≠ NP - det vil si bevise at noen NP-problemer ikke kan løses med noen mulig polynomisk algoritme - ved å bruke variasjoner på teknikkene Turing hadde brukt for å bevise at noen problemer ikke kan løses med noen algoritme overhodet. . Men de raskt oppdaget et bevis på at disse metodene ikke ville fungere - den første store barrieren for å løse P versus NP-spørsmålet. Så de begynte å lete etter en annen tilnærming, og de fant snart en i arbeidet til Turings samtidige claude shannon.

Shannon, som vokste opp i en liten by i det nordlige Michigan, virket som en usannsynlig skikkelse til å innlede informasjonsalderen. Likevel eksemplifiserte han den tverrfaglige karakteren til den nye disiplinen informatikk, og følte seg like hjemme innen elektroteknikk og matematisk logikk. I hans masteroppgave, viste Shannon hvordan kretser laget av elektromekaniske brytere kunne representere logiske uttrykk som involverer boolske variabler - mengder som bare kan ta på to verdier (som sant eller usant, eller 1 og 0).

I disse uttrykkene er boolske variabler koblet sammen av de "logiske portene" OG, ELLER og IKKE. Det elementære uttrykket A OG B, for eksempel, er sant når både A og B er sanne, og usant ellers; A ELLER B, derimot, er sann hvis minst én av de to variablene er sanne. En NOT-port er enda enklere: Den inverterer verdien til en enkelt variabel. Med nok av disse grunnleggende byggeklossene kan du utføre en hvilken som helst beregning.

"Når du ser på datamaskinen din, på slutten av dagen, hva gjør den? Det kjører en krets,” sa Ilango.

Shannons arbeid foreslo en ny måte for teoretikere å tenke på vanskelighetene ved beregningsproblemer, kalt "kretskompleksitet", selv om de aktuelle kretsene bare er matematiske abstraksjoner. En stund trodde forskerne at denne tilnærmingen kunne være måten å løse P versus NP, men til slutt løp stien opp mot den naturlige bevisbarrieren.

Kretskompleksitetsrammeverket krever å tenke nytt om de mest grunnleggende konseptene i Turings beregningsmodell. Her, i stedet for beregningsproblemer og algoritmene som løser dem, vurderer forskere boolske funksjoner og kretsene som beregner dem. En boolsk funksjon tar inn boolske variabler – sant og usant, 1s og 0s – og gir ut enten sant eller usant, 1 eller 0. Og som en algoritme, beskriver en krets en prosedyre for å produsere en utgang gitt hvilken som helst inngang.

"Min forståelse er at folk begynte å jobbe med kretskompleksitet fordi de bestemte at Turing-maskiner var for kompliserte," sa Ryan Williams, en kompleksitetsteoretiker ved MIT. "Vi kan studere kretser gate for gate."

Akkurat som det kan være mange algoritmer for å løse et gitt beregningsproblem, noen raskere enn andre, kan mange forskjellige kretser beregne en gitt boolsk funksjon, noen med færre porter enn andre. Forskere definerer kretskompleksiteten til en funksjon som det totale antallet porter i den minste kretsen som beregner den. For en funksjon med et fast antall inngangsvariabler er kretskompleksitet også et fast tall - høyere for noen funksjoner enn for andre.

Men i mange tilfeller kan du vurdere mer kompliserte versjoner av samme funksjon ved å øke antall inngangsvariabler, akkurat som du kan gjøre Hamilton-baneproblemet vanskeligere ved å vurdere større grafer. Forskere vurderer deretter det samme spørsmålet de stiller når de studerer algoritmekjøringstider: Vokser minimumsantallet av porter som trengs for å beregne en boolsk funksjon polynomisk eller eksponentielt ettersom antall inngangsvariabler øker? Forskere kaller disse to kategoriene av funksjoner henholdsvis "lett å beregne" og "vanskelig å beregne".

En lett å beregne boolsk funksjon ligner på et beregningsproblem i klassen P - et som kan løses med en algoritme som kjører i polynomisk tid. Men det er også funksjoner som er analoge med harde NP-problemer, der den beste måten forskere har oppdaget for å beregne stadig større versjoner krever et eksponentielt økende antall porter, men svaret kan lett sjekkes. Hvis kompleksitetsteoretikere kunne bevise at det virkelig ikke er noen bedre måte å beregne en slik funksjon på, ville det bety P ≠ NP.

Dette var strategien som de fleste kompleksitetsteoretikere fulgte på 1980-tallet. Og oddsen var på deres side. Shannon hadde beviste i 1949 at nesten hver boolsk sannhetstabell (som bare er en lang liste over alle mulige innganger og utganger til en boolsk funksjon med fast størrelse) har kretskompleksitet som er praktisk talt så høy som mulig. Han brukte et forbløffende enkelt argument: Det er langt færre måter å kombinere et lite antall porter på enn det er måter å kombinere mange porter på.

"Det er bare ikke nok små kretser til å gå rundt," sa Aaronson.

Så kompleksitetsteoretikere befant seg i en nysgjerrig situasjon. Hvis nesten hver sannhetstabell har høy kretskompleksitet, må nesten alle boolske funksjoner være vanskelige å beregne. Forskere måtte bare identifisere en enkelt slik funksjon som også var kjent for å være i klassen NP. Hvor vanskelig kan det være?

Crypto Bros

Til å begynne med gikk fremgangen raskt. I 1981, Sipser og to samarbeidspartnere beviste at en viss boolsk funksjon definitivt var vanskelig å beregne hvis de brukte kretser med visse begrensninger på hvordan porter kunne ordnes.

"Fantasien var at du ville være i stand til å bevise ting om disse begrensede modellene, og deretter bygge på det du har lært for å jobbe med færre og færre restriksjoner," sa Sipser.

I 1985 tok Razborov det neste store steget. Han hadde nettopp begynt på forskerskolen i Moskva og ble med på innsatsen ved et uhell mens han taklet et problem i en annen gren av matematikken, der det viste seg at det å løse P versus NP-problemet var en forutsetning.

"Jeg var rett og slett heldig at jeg ikke visste hvor vanskelig dette problemet var," sa Razborov. "Ellers hadde jeg kanskje ikke begynt engang."

Razborov analyserte kretser som bare inneholder OG- og ELLER-porter, og beviste at en bestemt funksjon var vanskelig å beregne ved bruk av slike kretser, uansett hvordan porter ble arrangert - dessuten var den funksjonen kjent for å være NP-komplett. Alt forskerne måtte gjøre for å løse P versus NP var å utvide Razborovs teknikker til kretser med IKKE porter.

"Det var en slags universell følelse av at ett skritt til, en streik til, og vi skal få det," sa Razborov. Men det var ikke det som skjedde. Razborov beviste selv at metoden hans ville mislykkes hvis IKKE porter ble lagt til blandingen, og ingen kunne finne en annen vei videre. Ettersom årene gikk, begynte han å lure på hvorfor stien hadde gått ut.

I USA tenkte Rudich på det samme spørsmålet. Han og Impagliazzo var klassekamerater på college som hadde gått på videregående skole sammen. Vennskapet deres hadde blitt utløst av en felles fascinasjon for Gödel og Turings selvrefererende bevis og deres implikasjoner for grunnlaget for matematikk og informatikk.

"Spøken vår var at vi skulle få en knapp som sa 'selvreferanse'," sa Impagliazzo.

Som hovedfagsstudenter jobbet både Rudich og Impagliazzo med det kompleksitetsteoretiske grunnlaget for kryptografi, et emne som kanskje gir den beste praktiske motivasjonen for å forsøke å bevise P ≠ NP. Kryptografer skjuler hemmelige meldinger ved å skjule dem i "pseudorandomness" - en melding kryptert på denne måten vil se ut som et tilfeldig virvar av tall for enhver avlytter, men den kan fortsatt dekodes av den tiltenkte mottakeren. Men hvordan kan du være sikker på at en potensiell avlytter vil finne det for vanskelig å knekke koden?

Det er her kompleksitetsteorien kommer inn. Krypteringsmetodene som er mest brukt i dag er alle basert på tilsynelatende vanskelige NP-problemer - for å dekryptere meldingen, ville en angriper trenge en ennå uoppdaget rask algoritme for å løse problemet. For å fastslå at disse metodene er virkelig sikre, en ting du må gjøre er å bevise at P ≠ NP. Uten et bevis, sa Sipser, er alt du kan gjøre "å håpe at den du prøver å holde hemmeligheten for ikke er en bedre matematiker enn deg."

Selv om det var fascinerende i seg selv, virket kryptografi langt unna de selvrefererende argumentene som først hadde trukket Rudich og Impagliazzo inn i feltet. Men da Rudich slet med å forstå hvorfor kretskompleksitetstilnærmingen hadde stoppet opp, begynte han å innse at de to fagene ikke var så langt fra hverandre likevel. Strategien forskerne hadde tatt i bruk i sine forsøk på å bevise at P ≠ NP hadde en selvødeleggende karakter som minner om Gödels berømte påstand «dette utsagnet kan ikke bevises» - og kryptografi kan bidra til å forklare hvorfor. I Russland oppdaget Razborov en lignende forbindelse omtrent på samme tid. Dette var frøene til den naturlige bevisbarrieren.

Spenningen i hjertet av den naturlige bevisbarrieren er at oppgaven med å skille funksjoner med høy kompleksitet fra funksjoner med lav kompleksitet ligner på oppgaven med å skille ekte tilfeldighet fra pseudorandomiteten som brukes til å kryptere meldinger. Vi vil gjerne vise at funksjoner med høy kompleksitet er kategorisk forskjellige fra funksjoner med lav kompleksitet, for å bevise P ≠ NP. Men vi vil også at pseudorandomness skal være umulig å skille fra tilfeldighet, for å være trygg på sikkerheten til kryptografi. Kanskje vi ikke kan ha det begge veier.

En grusom vits

I 1994 innså Razborov og Rudich at de hadde fått lignende innsikt, og de begynte å jobbe sammen for å kombinere resultatene. De observerte først at alle tidligere forsøk på å bevise P ≠ NP ved å bruke kretskompleksitet hadde tatt i bruk den samme generelle strategien: Identifiser en spesiell egenskap til en NP-komplett boolsk funksjon, og bevis deretter at ingen enkel å beregne funksjon muligens kunne dele den egenskapen. Det ville vise at den valgte NP-komplette funksjonen virkelig var vanskelig å beregne, noe som beviser P ≠ NP.

Sipser, Razborov og andre hadde brukt den samme strategien med hell for å bevise sine mer begrensede resultater, og i alle tilfeller ble den spesielle egenskapen som forskerne identifiserte delt av de fleste boolske funksjoner. Razborov og Rudich skapte begrepet "naturlig bevis" for å referere til denne saken der eiendommen var mye delt, rett og slett fordi det ikke var noe kjent alternativ. Hvis "unaturlige" bevis var mulige, måtte de være veldig kontraintuitive og fortjener navnet.

Razborov og Rudich beviste deretter hovedresultatet sitt: Et naturlig bevis på P ≠ NP ville kreve en svært omfattende forståelse av hvordan funksjoner som er enkle å beregne og vanskelig å beregne, og at kunnskap også kan gi en rask algoritme for å oppdage lett. -to-compute-funksjoner selv om de er overfladisk kompliserte. Hvis kompleksitetsteoretikere hadde lykkes med et naturlig bevis på P ≠ NP, ville de ha oppdaget en nesten ufeilbarlig måte å se på en vilkårlig sannhetstabell og finne ut om den tilsvarende funksjonen hadde høy eller lav kretskompleksitet - et mye sterkere og mer generelt resultat enn de hadde satt seg fore å bevise.

"Du kan nesten ikke la være å få mer enn du forhandlet om," sa Carmosino.

Det er som om du prøvde å faktasjekke en spesifikk påstand, men hvert forsøk ble til en blåkopi for en generell løgndetektor - det ville virke for godt til å være sant. For kompleksitetsteoretikere gjorde den overraskende kraften til naturlige bevis likeledes suksess mindre sannsynlig. Men hvis et slikt bevis hadde lykkes, ville de uventede konsekvensene være dårlige nyheter for kryptografi, på grunn av sammenhengen mellom kretskompleksitet og pseudotilfeldighet.

For å forstå denne sammenhengen, forestill deg å se på utdatakolonnen i sannhetstabellen til en boolsk funksjon med mange inngangsvariabler og erstatte hver "sann" med 1 og hver "usann" med 0:

Hvis den boolske funksjonen har høy kretskompleksitet, vil den lange listen med utganger i prinsippet ikke kunne skilles fra en virkelig tilfeldig streng med 0-er og 1-er - en som oppnås ved gjentatte ganger å snu en mynt, for eksempel. Men hvis funksjonen har lav kretskompleksitet, må strengen ha en enkel, kortfattet beskrivelse selv om den ser komplisert ut. Det gjør det veldig likt pseudorandom-strengene som brukes i kryptografi, hvis kortfattede beskrivelse er den hemmelige meldingen begravd i den tilsynelatende tilfeldigheten.

Så Razborov og Rudichs resultat viste at ethvert naturlig bevis på P ≠ NP også ville gi en rask algoritme som kunne skille pseudorandom-strenger som inneholder skjulte meldinger fra virkelig tilfeldige. Sikker kryptografi ville være umulig - akkurat det motsatte av hva forskere håpet å fastslå ved å bevise P ≠ NP.

På den annen side, hvis sikker kryptografi er mulig, så er ikke naturlige bevis en levedyktig strategi for å bevise P ≠ NP - en forutsetning for sikker kryptografi. Det er den naturlige bevisbarrieren i et nøtteskall. Det virket som om kompleksitetsteoretikere var på mottakersiden av en grusom spøk.

"Hvis du tror på hardhet, bør du tro at det er vanskelig å bevise hardhet," sa Kabanets.

Inn i Metaverse

Den forbindelsen mellom implikasjonene av P ≠ NP-formodningen og vanskeligheten med å bevise den var spennende, men vanskelig å finne ut. For det første blokkerte den naturlige bevisbarrieren bare én tilnærming til å bevise P ≠ NP. For en annen koblet det vanskeligheten med å bevise P ≠ NP ikke til P ≠ NP i seg selv, men til eksistensen av sikker kryptografi - et nært beslektet, men ikke helt ekvivalent problem. For å virkelig forstå sammenhengen, må forskere bli komfortable med metakompleksitet.

"Det er denne intuisjonen at 'å, fordi P ≠ NP, det er vanskelig å bevise at P ≠ NP," sa Williams. "Men for til og med å forstå denne intuisjonen, må du begynne å tenke på oppgaven med å bevise noe som P ≠ NP som et beregningsproblem."

Det var det Kabanets gjorde som hovedfagsstudent. Han hadde vokst opp i Ukraina, og han fullførte sine studier i informatikk to år etter Sovjetunionens fall. I uroen som fulgte, hadde han få muligheter til å forfølge de teoretiske temaene som interesserte ham mest.

"Jeg ønsket å gjøre noe mer akademisk," husket Kabanets. "Og jeg var også nysgjerrig på å se verden." Han flyttet til Canada for å studere, og det var der han lærte om barrieren for naturlige bevis. I likhet med Carmosino ble Kabanets betatt av resultatet. "Det virket veldig dypt at du har denne forbindelsen," sa han.

I 2000, mot slutten av tiden på grunnskolen, fant han ut at barrieren for naturlige bevis stadig dukket opp i samtalene hans med Jin-Yi Cai, en kompleksitetsteoretiker som besøkte Toronto på sabbatsår på den tiden. De begynte å se barrieren ikke som en veisperring, men som en invitasjon – en mulighet til å undersøke nøyaktig hvor vanskelig det var å bevise problemer. De papir der de la ut dette nye perspektivet, ville bli et av de mest innflytelsesrike tidlige verkene i det begynnende feltet av metakompleksitet.

Kabanets og Cais artikkel fremhevet et beregningsproblem implisitt i Razborov og Rudichs formulering av den naturlige bevisbarrieren: Gitt sannhetstabellen til en boolsk funksjon, avgjør om den har høy eller lav kretskompleksitet. De kalte dette problemet med minste kretsstørrelse, eller MCSP.

MCSP er et typisk metakompleksitetsproblem: et beregningsproblem hvis emne ikke er grafteori eller et annet eksternt emne, men selve kompleksitetsteorien. Det er faktisk som en kvantitativ versjon av spørsmålet som drev kompleksitetsteoretikere til å takle P versus NP ved å bruke kretskompleksitetstilnærmingen på 1980-tallet: Hvilke boolske funksjoner er vanskelige å beregne, og hvilke er enkle?

"Hvis vi kom opp med en MCSP-algoritme, ville det vært som en måte å automatisere det vi gjør innen kompleksitetsteori," sa Impagliazzo. "Det burde i det minste gi oss en enorm innsikt i hvordan vi kan gjøre jobben vår bedre."

Kompleksitetsteoretikere bekymrer seg ikke for at denne magiske algoritmen setter dem ut av arbeid - de tror ikke den eksisterer i det hele tatt, fordi Razborov og Rudich viste at enhver slik algoritme for å skille sannhetstabeller med høy kompleksitet fra lavkompleksitetstabeller ville lage kryptografi umulig. Det betyr at MCSP sannsynligvis er et vanskelig beregningsproblem. Men hvor vanskelig er det? Er det NP-komplett, som Hamilton-stiproblemet og nesten alle andre problemer som forskere slet med på 1960-tallet?

For problemer i NP, "hvor vanskelig er det?" er vanligvis lett nok å svare på, men MCSP så ut til å være en merkelig uteligger. "Vi har svært få "svevende rundt"-problemer som ikke har vært knyttet til denne øya av NP-komplette problemer, selv om de ser ut til å være vanskelige, sa Kabanets.

Kabanets visste at han og Cai ikke var de første som vurderte problemet de hadde kalt MCSP. Sovjetiske matematikere hadde studert et veldig lignende problem fra 1950-tallet, i et tidlig forsøk på å forstå den iboende vanskeligheten til forskjellige beregningsproblemer. Leonid Levin hadde kjempet med det mens han utviklet det som skulle bli teorien om NP-fullstendighet på slutten av 1960-tallet, men han kunne ikke bevise at den var NP-fullstendig, og han publiserte sin banebrytende artikkel uten den.

Etter det vakte problemet liten oppmerksomhet i 30 år, inntil Kabanets og Cai bemerket forbindelsen til den naturlige bevisbarrieren. Kabanets forventet ikke å avgjøre spørsmålet selv - i stedet ønsket han å utforske hvorfor det hadde vært så vanskelig å bevise at dette tilsynelatende vanskelige problemet med beregningshardhet faktisk var vanskelig.

"Det er på en måte meta-meta-kompleksitet," sa Rahul Santhanam, en kompleksitetsteoretiker ved University of Oxford.

Men var det hardheten helt ned, eller var det i det minste en måte å forstå hvorfor forskere ikke hadde lykkes i å bevise at MCSP var NP-komplett? Kabanets oppdaget at, ja, det var en grunn: Vanskeligheten med å forstå kretskompleksitet fungerer som en barriere for enhver kjent strategi for å bevise NP-fullstendigheten til MCSP - et problem som i seg selv handler om vanskeligheten med å forstå kretskompleksitet. Den vridde, selvødeleggende logikken til den naturlige bevisbarrieren virket uunngåelig.

Det er også mulig at MCSP ikke er NP-komplett, men det virker også usannsynlig - visse enklere varianter av problemet er allerede kjent for å være NP-komplett.

"Vi har bare ikke et fint sted å sette det som direkte relaterer det til alle de andre problemene vi studerer," sa Impagliazzo.

Kabanets hadde belyst den merkelige oppførselen til MCSP, men han visste ikke hvordan han skulle komme videre. Metakompleksitetsforskningen avtok til en vedlikeholdslading. Det ville blomstre igjen 16 år senere, da forskere oppdaget en overraskende forbindelse til et annet grunnleggende spørsmål: Hvor vanskelig er det å løse problemer hvis du bare bryr deg om å få det riktige svaret mesteparten av tiden?

War of the Worlds

For hverdagsproblemer er svar som fungerer mesteparten av tiden ofte gode nok. Vi planlegger pendlingene våre for typiske trafikkmønstre, for eksempel, ikke for verste fall.

De fleste kompleksitetsteoretikere er vanskeligere å tilfredsstille: De er bare fornøyd med å erklære et problem enkelt hvis de kan finne en rask algoritme som får det riktige svaret på alle mulige input. Den standardtilnærmingen klassifiserer problemer i henhold til det forskerne kaller "worst-case" kompleksitet. Men det er også en teori om "gjennomsnittlig tilfelle"-kompleksitet, der problemer anses som enkle hvis det er en rask algoritme som får det riktige svaret på de fleste innganger.

Skillet er viktig for kryptografer. Se for deg et beregningsproblem som er enkelt å løse for nesten alle inndata, bortsett fra noen få gjenstridige tilfeller der den beste algoritmen mislykkes. Worst-case kompleksitetsteori anser det som et vanskelig problem, men for kryptografi er det ubrukelig: Hvis bare noen av meldingene dine er vanskelige å tyde, hva er poenget?

Det var faktisk Levin som startet den strenge studien av gjennomsnittlig sakskompleksitet, et tiår etter hans banebrytende arbeid med NP-fullstendighet. I de mellomliggende årene hadde han vært på kant med sovjetiske myndigheter - han var en uærbødig bråkmaker som av og til ville undergrave patriotiske aktiviteter i sin ungdomsgruppe i kommunistpartiet. I 1972 ble han nektet doktorgraden av eksplisitt politiske grunner.

"For å lykkes i Sovjetunionen som en ung forsker, kan du ikke være veldig selvstendig, og det er vanskelig å forestille seg at Leonid ikke er selvstendig," sa Impagliazzo.

Levin emigrerte til USA i 1978, og på midten av 1980-tallet vendte han oppmerksomheten mot gjennomsnittlig sakskompleksitet. Han begynte å jobbe med andre for å videreutvikle teorien, inkludert Impagliazzo, en hovedfagsstudent på den tiden. Men selv mens de gjorde fremskritt, fant Impagliazzo ut at forskere ofte snakket forbi hverandre. Han ønsket å få alle på samme side, og det hjalp ikke at Levins papirer var berømt kortfattede - den som startet feltet av gjennomsnittlig sakskompleksitet var mindre enn to sider lang.

"Jeg skulle gjøre en oversettelse av Leonids arbeid til mer tilgjengelige tekniske termer," sa Impagliazzo. Han bestemte seg for å starte med en kort, leken oversikt over det store bildet før han stupte ned i matematikken. "Den slags tok over avisen, og det er den eneste delen noen husker uansett."

De papir, utgitt i 1995, ble en umiddelbar klassiker. Impagliazzo laget lunefulle navn for fem verdener kjennetegnes ved forskjellige grader av beregningshardhet og forskjellige kryptografiske evner. Vi lever i en av disse verdenene, men vi vet ikke hvilken.

Helt siden Impagliazzos papir dukket opp, har forskere drømt om å eliminere deler av hans miniatyr-multivers – begrense mulighetene ved å bevise at noen av verdenene ikke er mulige likevel. To verdener er spesielt fristende mål: de der kryptografi er umulig selv om P ≠ NP.

I en av disse verdenene, kalt Heuristica, er alle NP-komplette problemer lette å løse på de fleste innganger, men raske algoritmer gjør av og til feil, så disse problemene anses fortsatt som vanskelige i forhold til standardene for worst-case kompleksitetsteori. Dette er verden der kryptografi er umulig fordi nesten hver kode lett blir knekket. I den andre verdenen, kalt Pessiland, er kryptografi umulig av en annen grunn: Hvert problem er vanskelig i gjennomsnittlig forstand, men kryptering av en melding gjør den uleselig selv for den tiltenkte mottakeren.

Disse to verdenene viser seg å være nært knyttet til metakompleksitetsproblemer - spesielt er skjebnen til Heuristica knyttet til det langvarige spørsmålet om MCSP er NP-komplett. Spørsmålet som fascinerte Kabanets og stusset Levin for så lenge siden er ingen ren nysgjerrighet: Det er en hel verden som står på spill.

For å utelukke Heuristica, ville forskere måtte kollapse skillet mellom verste tilfelle og gjennomsnittlig tilfelle kompleksitet - det vil si at de må bevise at enhver hypotetisk algoritme som løser et NP-komplett problem riktig på de fleste input faktisk kan løse det i alle tilfeller. Denne typen forbindelse, kalt en worst-case til gjennomsnittlig case-reduksjon, er kjent for å eksistere for visse problemer, men ingen av dem er NP-fullstendige, så disse resultatene innebærer ikke noe mer generelt. Å eliminere Heuristica ville ta kryptografer halvveis til å realisere drømmen om sikker kryptering basert på den enkle antakelsen om at P ≠ NP.

Men å ødelegge en verden er ingen liten prestasjon. I 2003, to kompleksitetsteoretikere viste at eksisterende tilnærminger for å bevise reduksjoner fra verste fall til gjennomsnittlige tilfeller for kjente NP-komplette problemer ville innebære merkelige konsekvenser, noe som antyder at slike bevis sannsynligvis ikke er mulige.

Forskere måtte finne en annen tilnærming, og de tror nå at MCSP kan være akkurat problemet de trenger. Men det ville ikke bli klart før over et tiår. Det første glimtet av forbindelsen kom fra Marco Carmosinos vedvarende fascinasjon for den naturlige bevisbarrieren.

Carmosino møtte først metakompleksitetsforskning som doktorgradsstudent gjennom en 2013 papir av Kabanets og fire andre forskere, som videreutviklet tilnærmingen til den naturlige bevisbarrieren som Kabanets hadde vært pioner for mer enn et tiår tidligere. Det bare styrket hans overbevisning om at det fortsatt var mer å lære av Razborov og Rudichs klassiske papir.

"Jeg var besatt av det papiret på den tiden," sa Carmosino. "Ingenting har forandret seg."

Besettelsen bar endelig frukt under et besøk på en semesterlang workshop ved University of California, Berkeley, hvor han brukte mesteparten av tiden sin på å snakke med Impagliazzo, Kabanets og Antonina Kolokolova, en kompleksitetsteoretiker ved Memorial University of Newfoundland som hadde samarbeidet med Kabanets på papiret fra 2013. Carmosino hadde jobbet med de tre en gang tidligere, og det vellykkede samarbeidet ga ham selvtilliten til å pepre dem med spørsmål om temaet som fascinerte ham mest.

"Han plaget folk på en god måte," husket Kabanets.

Til å begynne med hadde Carmosino nye ideer for å bevise NP-fullstendighet for versjonen av MCSP som hadde dukket opp i Razborov og Rudichs papir om den naturlige bevisbarrieren. Men de ideene gikk ikke ut. I stedet fikk en kommentar fra Impagliazzo de fire forskerne til å innse at den naturlige bevisbarrieren kunne gi kraftigere algoritmer enn noen hadde innsett - det var et hemmelig kart etset inn i veisperringen.

I en 2016 papir, beviste de fire forskerne at en viss type MCSP-algoritme med gjennomsnittlig tilfelle kunne brukes til å konstruere en verstefallsalgoritme for å identifisere mønstre som er skjult i tilfeldig utseende strenger av sifre - en oppgave som informatikere refererer til som "læring." Det er et slående resultat fordi læring intuitivt virker vanskeligere enn den binære klassifiseringsoppgaven – høy kompleksitet eller lav kompleksitet – utført av en MCSP-algoritme. Og overraskende nok koblet den den verste kompleksiteten til en oppgave til den gjennomsnittlige kompleksiteten til den andre.

"Det var ikke åpenbart at en slik forbindelse ville eksistere i det hele tatt," sa Impagliazzo.

En rask algoritme for MCSP er rent hypotetisk for generelle boolske kretser: Den kan ikke eksistere med mindre MCSP viser seg å være et enkelt beregningsproblem, til tross for alle bevis på det motsatte, og det betyr at læringsalgoritmen som er implisert av de fire forskernes artikkel er like hypotetisk.

Men for noen enklere versjoner av MCSP – som skiller sannhetstabeller med høy kompleksitet fra lavkompleksiteter når det er spesifikke begrensninger på kretsene – har raske algoritmer vært kjent i mange år. Carmosino, Impagliazzo, Kabanets og Kolokolovas artikkel viste at disse algoritmene kunne transformeres til læringsalgoritmer som på samme måte var begrenset, men fortsatt kraftigere enn noen som forskere tidligere hadde forstått på et så strengt teoretisk nivå.

"På en eller annen måte lar deres selvrefererende smak deg gjøre ting som du tilsynelatende ikke kan gjøre med mer standardproblemer," sa Ilango.

Resultatet fanget oppmerksomheten til kompleksitetsteoretikere som jobbet med andre emner. Det var også en forhåndsvisning av ytterligere sammenhenger mellom metakompleksitet og gjennomsnittlig sakskompleksitet som ville dukke opp i løpet av de kommende årene.

Mest av alt var det et vitnesbyrd om hvor langt forskere kan komme ved å stille enkle spørsmål om barrierer som til å begynne med bare ser ut til å hindre deres fremgang.

"Denne typen dualitet er et tema gjennom minst de siste 30 eller 40 årene med kompleksitet," sa Impagliazzo. "Hindrene er ofte mulighetene."

Delvis kreditt

Fremgangen har bare akselerert i årene siden Carmosino og hans kolleger publiserte papiret sitt.

"Nye ting skjer," sa Kolokolova. "Det er mange virkelig, virkelig dyktige juniorforskere."

Ilango er en av disse unge forskerne – i løpet av de tre første årene av forskerskolen har han angrepet det skremmende åpne problemet med å bevise MCSP NP-fullstendig ved å bruke en todelt strategi: bevise NP-fullstendighet for enklere versjoner av MCSP, slik kretskompleksitetsforskere gjorde da de angrep P mot NP på 1980-tallet, samtidig som de beviste NP-fullstendighet for mer kompliserte versjoner, som intuitivt virker vanskeligere og dermed er kanskje lettere å bevise hardt.

Ilango krediterer sin interesse for metakompleksitet Eric Allender, en kompleksitetsteoretiker ved Rutgers University og en av få forskere som fortsatte å jobbe med metakompleksitet på 2000-tallet og begynnelsen av 2010-tallet. "Hans entusiasme var smittende," sa Ilango.

En annen ung forsker inspirert av Allender er Shuichi Hirahara, nå professor ved National Institute of Informatics i Tokyo. Mens han fortsatt var en doktorgradsstudent i 2018, avslørte Hirahara det sanne omfanget av forholdet mellom metakompleksitet og gjennomsnittlig sakskompleksitet som Carmosino og hans medforfattere hadde oppdaget. De fire forskerne hadde funnet en sammenheng mellom den gjennomsnittlige kompleksiteten til ett problem – MCSP – og den verste tilfellet til et annet – boolsk læring. Hirahara utviklet teknikkene sine videre til Derive en reduksjon fra verste til gjennomsnittet for MCSP. Resultatet hans antyder at en hypotetisk gjennomsnittlig MCSP-algoritme som den Carmosino og kollegene hans hadde vurdert, faktisk ville være kraftig nok til å løse en litt annen versjon av MCSP uten å gjøre noen feil.

Hiraharas resultat er spennende fordi mange forskere mistenker at MCSP er NP-komplett, i motsetning til alle andre problemer der det er kjent reduksjoner fra verste til gjennomsnittlige tilfeller. Hvis de kan utvide Hiraharas resultater til å dekke alle gjennomsnittlige algoritmer og deretter bevise at MCSP er NP-komplett, vil det bevise at vi ikke bor i Heuristica.

"Det ville virkelig være et verdensomspennende resultat," sa Santhanam.

Å bevise at MCSP er NP-komplett kan virke som en stor ordre - tross alt har spørsmålet vært åpent i over 50 år. Men etter en gjennombrudd i fjor av Hirahara, er forskere nå mye nærmere enn noen ville ha forventet for noen år siden.

Hirahara beviste NP-fullstendighet for en variant av problemet kalt delvis MCSP, der du ignorerer visse oppføringer i hver sannhetstabell. Beviset hans bygget på metoder utviklet av Ilango for å vise at delvis MCSP tilsvarte et tilsynelatende urelatert problem som involverte en kryptografisk teknikk kalt hemmelig deling. Dette er en måte å dele en kryptert melding mellom mange mennesker slik at den bare kan dekodes hvis en viss brøkdel av dem jobber sammen.

For enhver ekte applikasjon innen kryptografi, vil du gjerne vite den brøkdelen på forhånd, men ved hjelp av ekstra kryptografiske triks kan du konstruere et frustrerende scenario der det er vanskelig bare å finne ut hvor mange mennesker som trenger å samarbeide. Hirahara fant en måte å bevise at dette konstruerte kryptografiske problemet var NP-komplett, og viste deretter at beviset antydet NP-fullstendigheten til delvis MCSP også.

Dette resultatet ga forskere i metakompleksitet enda mer energi enn Hiraharas tidligere arbeid, og andre forskere la også merke til det - kompleksitetsteoretikeren og bloggeren Lance Fortnow kalte det årets resultat. Det er fordi å takle slike "delfunksjons"-versjoner av beregningsproblemer har vært et sentralt mellomtrinn i andre bevis på NP-fullstendighet.

"Det er fantastisk arbeid," sa Williams. "Alle trodde at disse delvise problemene var omtrent samme vanskelighetsgrad som hele problemet."

Det gjenstår hindringer for å bevise NP-fullstendighet for fullversjonen av MCSP. Men ingen er den typen barrierer som antyder at et helt nytt verktøysett er nødvendig - det kan bare være et spørsmål om å finne den rette måten å kombinere kjente teknikker på. Et bevis ville endelig avgjøre statusen til et av de få problemene som har motstått klassifisering så lenge kompleksitetsteori har eksistert. Over e-post skrev Levin: "Det ville ydmyke meg å vise at jeg var dum for ikke å ha vært i stand til å se det :-)."

De manglende stykkene

MCSP er ikke engang det eneste metakompleksitetsproblemet som har ansporet til et stort gjennombrudd. I 2020, Cornell Tech-kryptografen Rafael Pass og hans hovedfagsstudent Yanyi Liu oppdaget en sammenheng mellom et annet metakompleksitetsproblem og en grunnleggende kryptografisk protokoll som definerer grensen mellom Heuristica og Pessiland, den verste av Impagliazzos verdener (hvor NP-komplette problemer er vanskelige i gjennomsnittlig forstand, men kryptografi fortsatt er umulig). Det gjør problemet de studerte til en hovedkandidat for et angrep på Pessiland, og deres nyere arbeid indikerer at det kan virke mot Heuristica også.

"Ulike brikker i puslespillet mangler," sa Pass. "For meg er det bare magisk at disse feltene er så nært knyttet sammen."

Hirahara advarer om at utfordringer fortsatt venter på forskere som har til hensikt å utrydde verdener som Impagliazzo tryllet frem for 30 år siden. "Jeg vil gjerne si at Heuristica og Pessiland på et tidspunkt vil bli utelukket, men jeg er ikke sikker på hvor nærme vi er," sa han.

Mange forskere forventer at den største vanskeligheten vil være å bygge bro over et tilsynelatende ufarlig gap mellom to forskjellige modeller for gjennomsnittlig sakskompleksitet. Kryptografer studerer vanligvis gjennomsnittlige kasusalgoritmer som gjør feil i begge retninger, og av og til feilmerker tilfeldige strenger som pseudorandom og omvendt. Hiraharas reduksjoner fra verste til gjennomsnittlige tilfeller fungerer i mellomtiden for algoritmer for gjennomsnittlige tilfeller som bare gjør den første typen feil. Subtile distinksjoner som dette kan gjøre en verden av forskjell i kompleksitetsteori. Men til tross for dette hinderet og mange andre, kan ikke Allender la være å høre en bevoktet optimisme.

"Jeg prøver å ikke la meg være for mye troende fordi det er en ganske veletablert track record på at ingenting fungerer," sa han. "Men vi ser mange virkelig spennende utviklinger - måter å overvinne ting som så ut som barrierer."

Hvis det er én lekse forskerne har lært av kampene deres for å svare på P versus NP-spørsmålet – eller til og med bare forstå det – så er det at kompleksitetsteori i seg selv er kompleks. Men den utfordringen er nettopp det som gjør oppdraget så givende.

"Det er faktisk litt flott at det er så vanskelig," sa Carmosino. "Jeg kommer aldri til å kjede meg."

Redaktørens notat: Scott Aaronson er medlem av Quanta Magazine'S rådgivende styre.