Det 50 år gamle problemet som unnslipper teoretisk informatikk

En løsning på P vs NP kan låse opp utallige beregningsproblemer – eller holde dem utenfor rekkevidde for alltid.

Steiner-treproblemet: Koble sammen et sett med punkter med linjestykker med minimum total lengde. Derek Brahney

av

• Siobhan Roberts arkivside

27. oktober 2021

en. Mandag 19. juli 2021, midt i en annen merkelig pandemisommer, twitret en ledende informatiker innen kompleksitetsteori ut en offentlig tjenestemelding om et administrativt uhell i et tidsskrift. Han kvitterte med en svært lastet

God mandag.

Denne historien var en del av november 2021-utgaven vår

• Se resten av saken
• Abonnere

I et parallelt univers hadde det kanskje vært en veldig glad mandag. Et bevis hadde dukket opp på nettet i det anerkjente tidsskriftet ACM Transactions on Computational Theory, som handler med fremragende original forskning som utforsker grensene for gjennomførbar beregning. Resultatet påsto å løse problemet med alle problemer - den hellige gral for teoretisk datavitenskap, verdt en pris på 1 million dollar og berømmelse som konkurrerer med Aristoteles for alltid.

Dette dyrebare problemet – kjent som P versus NP – anses på en gang som det viktigste innen teoretisk informatikk og matematikk og helt utenfor rekkevidde. Den tar opp spørsmål som er sentrale for løftet, grensene og ambisjonene for beregning, og spør:

Hvorfor er noen problemer vanskeligere enn andre?

Hvilke problemer kan datamaskiner løse realistisk?

Hvor lang tid vil det ta?

Og det er et oppdrag med store filosofiske og praktiske gevinster.

Se, dette P versus NP-spørsmålet, hva kan jeg si? Scott Aaronson, en dataforsker ved University of Texas i Austin, skrev i sin memoarer av ideer , Kvanteberegning siden Demokrit . Folk liker å beskrive det som «sannsynligvis det sentrale uløste problemet med teoretisk informatikk.» Det er en komisk underdrivelse. P vs NP er et av de dypeste spørsmålene mennesker noen gang har stilt.

En måte å tenke på denne historiens hovedpersoner er som følger:

P representerer problemer som en datamaskin lett kan løse.

NP representerer problemer som, når de er løst, er enkle å sjekke – som puslespill eller Sudoku. Mange NP-problemer tilsvarer noen av de mest sta og presserende problemene samfunnet står overfor.

Million-dollar-spørsmålet som stilles av P vs. NP er dette: Er disse to problemene en og samme? Det vil si, kunne problemene som virker så vanskelige faktisk løses med en algoritme i løpet av rimelig tid, hvis bare den rette, djevelsk raske algoritmen kunne bli funnet? I så fall kan mange vanskelige problemer plutselig løses. Og deres algoritmiske løsninger kan føre til samfunnsendringer av utopiske proporsjoner – innen medisin og ingeniørvitenskap og økonomi, biologi og økologi, nevrovitenskap og samfunnsvitenskap, industri, kunst, til og med politikk og utover.

Noen ganger utvikler klassifikasjonene seg – vanskelige problemer viser seg å være enkle når forskere finner mer effektive løsninger. Å teste om et tall er primtall, har for eksempel vært kjent for å være i klassen NP siden midten av 1970-tallet. Men i 2002 utviklet tre informatikere ved Indian Institute of Technology Kanpur et ubetinget bevis og en smart algoritme som til slutt bekreftet at problemet også var i P.

Hvis alle de vanskelige problemene kunne forvandles med en slik algoritmisk slenghendelse, konsekvensene for samfunnet – for menneskeheten og planeten vår – ville være enorme.

For det første ville krypteringssystemer, hvorav de fleste er basert på NP-problemer, bli sprukket. Vi må finne en helt annen tilnærming til å sende sikker kommunikasjon. Proteinfolding, en 50 år gammel stor utfordring innen biologi, ville bli mer håndterbar, og låse opp nyvunne evner til å designe medisiner som kurerer eller behandler sykdom og oppdage enzymer som bryter ned industriavfall. Det vil også bety å finne optimale løsninger på hverdagens vanskelige problemer, som å kartlegge en biltur for å treffe alle destinasjoner med minimal kjøring, eller sette plass til bryllupsgjester slik at bare venner deler det samme middagsbordet.

Siden P vs. NP-problemet startet for 50 år siden – som dukket opp fra det betydningsfulle skjæringspunktet mellom matematisk logikk og elektronisk datateknologi – har forskere over hele verden gjort herkuliske forsøk på en løsning. Noen informatikere har antydet at innsatsen kan sammenlignes bedre med de til Sisyfos, som arbeidet uten løsning. Men mens de som først utforsket problemet går tom for tid til å se en løsning, tar de nye generasjonene med glede opp søket.

For Manuel Sabin, en informatiker som nettopp har fullført en doktorgrad ved UC Berkeley, er lokket i å undersøke umuligheten av problemer der du ikke vil vite svaret før solen oppsluker jorden. Søket kan være quixotisk, men Sabin ville angre på at han ikke vippet ved disse vindmøllene.

Timothy Gowers, en matematiker ved University of Cambridge, kaller det en av mine personlige matematiske sykdommer. Han tapte sommeren 2013 til jakten, etter at han ba studentene om et essay om emnet på en prøve. Som han fortalte på bloggen sin: Etter å ha markert essayene i juni, tenkte jeg at jeg bare skulle bruke en time eller to på å tenke på problemet igjen, og den timen eller to ble ved et uhell til omtrent tre måneder.

Problemet med den reisende selgeren: Finn den korteste mulige ruten som besøker hver by én gang, og returner til slutt til opprinnelsesbyen.

DEREK BRAHNEY

Oppdraget har til og med stusset informatikeren Stephen Cook ved University of Toronto, som rammet inn problemet og lanserte feltet for beregningskompleksitet med en banebrytende artikkel i 1971. For dette arbeidet vant han Turing-prisen, informatikks ekvivalent til Nobelprisen. Men han har ikke lyktes med å finne en løsning. Cook sier at han aldri hadde noen gode ideer - det er bare for vanskelig.

to. Michael Sipser, en MIT-dataforsker, anslår at han har brukt så mye som et tiår på problemet. Han ble interessert på grunnskolen på 1970-tallet, og han satset medstudenten Len Adleman en unse gull på at det ville være løst innen slutten av århundret (Sipser betalte).

På 1980-tallet oppnådde han et fint resultat med å løse en versjon av problemet med en begrenset beregningsmodell – noe som førte til en spennende periode i feltet med flere flotte resultater, noe som ga grunn til håp om at en løsning kanskje ikke er for langt unna.

Sipser vender fortsatt tilbake til problemet nå og da, og han er en standhaftig ambassadør som holder utallige foredrag om emnet.

Måten han går inn på en tilgjengelig forklaring av P vs. NP på er med et grunnleggende multiplikasjonsproblem: 7 × 13 = ?

Svaret, 91, er enkelt nok å beregne i hodet ditt. Selv om det ikke er like enkelt å multiplisere større tall, vil det fortsatt ta en datamaskin praktisk talt ingen tid i det hele tatt.

Men å snu disse problemene er en annen sak. Vurder for eksempel å finne de to 97-sifrede primtallene som multipliserer for å produsere dette veldig store tallet:

0437213507 5003588856 7930037346 310 7418240490 0228427275 4572016194 8823206440 5180815045 5634682967 1723286782 4379162728 3803341547 1073108501 9195485290 0733772482 2783525742 3864540146 9173660247 7652346609

Dette factoring-problemet var en del av en utfordring med å vurdere vanskeligheten med å knekke RSA-nøklene som brukes i kryptografi. Å løse det tok 80 prosessorer fem måneder med kontinuerlig databehandling, forklarer Sipser – noe som går ut på omtrent 33 år med bare en enkelt prosessor. Factoring er et vanskelig problem fordi alle nåværende metoder søker svaret via brute force, og sjekker det astronomiske antallet muligheter én etter én. Selv for en datamaskin er dette en langsom prosess.

Det interessante spørsmålet her er, trenger du virkelig å søke? Sipser sier. Eller er det en måte å løse factoring-problemet på som zoomer inn på svaret raskt uten å søke? Vi vet ikke svaret på det spørsmålet.

Spørsmål som dette er kjernen av beregningsmessig kompleksitet - et felt fullt av dyriske problemer som forskere prøver å forstå. Aaronson har satt sammen en Complexity Zoo, en online katalog med 545 klasser av problemer (og teller). Hver er klassifisert etter dens kompleksitet, eller vanskelighetsgrad, og ressursene – tid, minne, energi – som kreves for å finne løsninger. P og NP er hovedattraksjonene.

Som vitenskapelig serendipitet ville ha det, konvergerte en sovjetisk matematiker, Leonid Levin, et resultat tilsvarende Cooks på mer eller mindre samme tid.

P er klassen som startet det hele. Det er klassen av problemer som kan løses av en datamaskin på rimelig tid. Mer spesifikt er P-problemer de hvor tiden det tar å finne en løsning kan beskrives med en polynomfunksjon, som f.eks. n ^2. I polynom-tidsalgoritmer, n er størrelsen på inputen, og veksten mot den inputen skjer med en rimelig hastighet (i dette tilfellet i kraft av to).

Derimot kan noen harde NP-problemer bare løses av algoritmer med kjøretider definert av en eksponentiell funksjon, for eksempel 2^n - som produserer en eksponentiell vekstrate (som med spredningen av covid). NP, som Aaronson beskriver det, er klassen av knuste håp og tomme drømmer. Han er imidlertid raskt ute med å avklare en vanlig misforståelse: ikke alle NP-problemer er vanskelige. Klassen NP inneholder faktisk klassen P—fordi problemer med enkle løsninger er selvfølgelig også enkle å sjekke.

NPs mer utfordrende problemer har ofte betydningsfulle praktiske anvendelser. For disse problemene vil et uttømmende søk etter en løsning sannsynligvis pågå i upraktisk lang tid – geologisk tid – før det ble gitt et svar. Hvis en brute-force søkealgoritme er den beste mulige algoritmen, er ikke P lik NP.

Og blant cognoscenti er det tilsynelatende konsensus, som noen sammenligner mer med religiøs tro: P ≠ NP. De fleste tillater bare et snev av håp om at det motsatte vil vise seg sant. Jeg vil gi det en 2 til 3 % sjanse for at P er lik NP, sier Aaronson. Det er oddsen jeg vil ta.

Resultatet publisert i juli ga et bevis på akkurat det langskuddet. Men det var bare det siste i en lang tradisjon med bevis som ikke består. I løpet av en dag etter publisering, i en hendelsesvending som var Monty Python verdig, ble avisen fjernet fra nettjournalen; så det så ut til å dukke opp igjen en kort stund før den forsvant permanent. Det var den nyeste versjonen av en artikkel som forfatteren hadde lagt ut mer enn 60 ganger på arXiv preprint-server i løpet av det siste tiåret. Tidsskriftets sjefredaktør forklarte på Twitter at resultatet var avvist, men i et tilfelle av menneskelig feil hadde avisens disposisjon på en eller annen måte endret seg fra avvisning til aksept, og beviset hadde funnet veien til publisering.

3. I begynnelsen av august, da jeg møtte Steve Cook på kontoret hans på campus, hadde han verken sett eller hørt om det siste P vs. NP-beviset uheld. Nå 81, hadde han nylig pensjonert seg, siden hukommelsen hans sviktet. Det er derfor vi har James her, sa han - hans sønn James, 36, også en dataforsker, hadde blitt med oss ​​på besøket mitt. Steve var midt i å rydde kontoret sitt. En gigantisk resirkuleringsbøtte sto midt i rommet og fylte opp med gamle gulnende utgaver av Journal of Symbolic Logic, en stabel med superfete telefonbøker fra Toronto som ventet i nærheten.

Gjennom årene har Cook sett mange bevis som påstår å løse P vs. NP-problemet. I 2000, etter at Clay Mathematics Institute kalte det et av de syv uløste tusenårsproblemene (hver verdt en premie på 1 million dollar), ble han oversvømmet med meldinger fra folk som trodde de hadde seiret. Alle resultatene var feil, om ikke rett og slett falske. Omtrent halvparten hevdet å ha bevist at P er lik NP; den andre halvparten gikk i motsatt retning. For ikke så lenge siden hevdet en person å ha bevist begge deler.

Cook antok i sin artikkel fra 1971 at P ikke er lik NP (han formulerte det ved å bruke annen terminologi som var vanlig på den tiden). Han har siden investert en betydelig om ubestemt tid på å jobbe for å fastslå at det er tilfelle. Jeg har ikke noe godt minne om å slite, sier han, men kollegene husker at hver gang de gikk inn på avdelingen i helgen, var Steve der på kontoret sitt.

Med mindre han kjører kappseilbåter, er ikke Cook en som haster; han liker å gi en idé tid. Og hans tidligere elever husker en tydelig mangel på svada. Informatikeren Anna Lubiw, ved University of Waterloo, sier at da han underviste i Cooks teorem – en del av det banebrytende papiret – refererte han aldri til det som sådan og ga aldri noen hint om at han var personen som beviste det. Maria Klawe, en matematiker og informatiker og presidenten for Harvey Mudd College, sier at hun jevnlig ville korrigere Cook når han gikk seg vill og lærte bevis på at han visste ut og inn: Han ble sittende fast og sa: 'Ok. Fortell meg hvordan beviset går.’ Cook var også kjent beskjeden i søknader om stipend og rapporter knyttet til forskningen hans – han ville innrømmet: Ærlig talt, jeg har gjort små fremskritt …

Relatert historie

Evolusjonen av informatikk Å beregne energinivåene til et heliumatom i 1958 var betydelig vanskeligere enn det er i dag. Men en sammenligning av da og nå metoder avslører noen kontraintuitive anomalier om virkningen av informatikk.

Han gjorde imidlertid fremskritt med å rekruttere James til å ta opp saken. Tidlig viste James interesse for matematikk og databehandling - i en alder av ni oppfordret han faren sin til å lære ham boolsk algebra og logikk. For et par år siden, etter å ha tatt en doktorgrad ved Berkeley og gjort en stint hos Google, satte han i gang som en uavhengig forsker med fokus på diverse prosjekter, noen av dem indirekte knyttet til P vs. NP. Og til tross for merittrekorden, er James, som har en slående likhet med sin far, uforferdet over å ha arvet et slikt tilsynelatende uendelig oppdrag. Han ser på det som han ville gjort med enhver matematisk bestrebelse: det er et morsomt puslespill. Det må finnes svar på disse spørsmålene, sier han. Og det er som, kom igjen, noen må løse det. La oss bare finne ut av dette. Det er lenge siden. Det er flaut at vi ikke vet svaret ennå.

Mangelen på fremgang har ikke stoppet dette fellesskapet av glade sisyfer fra å feire beregningskompleksitetens 50-årsjubileum. Festlighetene begynte i 2019, da hengivne fra hele verden samlet seg ved Fields Institute for Research in Mathematical Sciences, ved University of Toronto, for et symposium til Cooks ære. Christos Papadimitriou, en informatiker ved Columbia University som har brukt mye av sin karriere på å jobbe med P vs. NP, åpnet arrangementet med et offentlig foredrag, og ser tilbake ikke et halvt århundre, men årtusener.

Han begynte med å beskrive eldgamle oppdrag etter løsninger – ved å bruke algebraiske verktøy eller rette og kompass, som han betraktet som rudimentære beregningsformer. Papadimitrious fortelling ankom til slutt Alan Turing, den britiske matematikeren hvis papir fra 1936 On Computable Numbers formaliserte forestillingene om algoritme og beregning. Turing viste også – med sin idé om en universell datamaskin – at det ikke finnes noen mekanisk måte (det vil si utført av en maskin) for å bevise sannheten eller usannheten til matematiske utsagn; ingen systematisk måte å skille det bevisbare fra det ubeviselige.

Papadimitriou sa at han anser Turings papir som fødselsattesten for informatikk - og fødselsattesten sier at informatikk ble født med en sterk forståelse av sine egne begrensninger. Han mente informatikk er det eneste kjente feltet for vitenskapelig diskurs som er født med en slik bevissthet - i motsetning til andre vitenskaper, som forstår sine egne begrensninger, som resten av oss, i sen middelalder.

Det tok ikke lang tid etter at Turings ideer (og lignende ideer fra andre) fant legemliggjøring i de første datamaskinene at forskere konfronterte spørsmål om maskinenes iboende evner og begrensninger. På begynnelsen av 1950-tallet skrøt John von Neumann, den ungarsk-amerikanske pioneren innen den moderne datamaskinen, av en algoritme for at han var polynom, sammenlignet med den eksponentielle sittende, som Papadimitriou husket - han hadde overlistet en langsom algoritme med en rask. Dette var begynnelsen på en ny teori: beregningskompleksitetsteori. Kjernen med det var at bare polynomiske algoritmer på noen måte er gode eller praktiske eller verdt å sikte på et problem, mens en eksponentiell algoritme, sa Papadimitriou, er den algoritmiske ekvivalenten til død.

Cook begynte først å tenke på kompleksitet på midten av 1960-tallet. Mens han jobbet med sin doktorgrad ved Harvard, vurderte han om det er mulig å bevise, gitt visse beregningsmodeller, at multiplikasjon er vanskeligere enn addisjon (det er fortsatt et åpent problem).

I 1967, ifølge en bok om Cook som kommer fra Association for Computing Machinery (ACM), mens han var postdoc ved Berkeley, utarbeidet han kursnotater som inneholdt kimen til hans store resultat. Han hadde utarbeidet en formulering av kompleksitetsklassene som ble kjent som P og NP, og han stilte spørsmålet om P var lik NP. (Omtrent på samme tid sirklet andre, inkludert informatikeren Jack Edmonds, nå pensjonert fra University of Waterloo, rundt de samme ideene.)

Men feltet for informatikk var bare så vidt i gang, og for de fleste forskere og matematikere var slike ideer ukjente om ikke direkte merkelige. Etter fire år ved Berkeleys matematiske avdeling, ble Cook vurdert for ansettelse, men ikke tilbudt en stilling. Han hadde talsmenn i universitetets nye avdeling for informatikk, og de drev lobbyvirksomhet for at han skulle få en stilling i deres rekker, men dekanen var ikke tilbøyelig til å gi funksjonstid til noen som de berømte matematikerne hadde nektet.

De fleste kompleksitetsteoretikere drømmer litt mindre, og velger i stedet indirekte tilnærminger.

I 1970 flyttet Cook til University of Toronto. Året etter publiserte han sitt gjennombrudd. Innsendt til et symposium av ACM holdt i mai i Shaker Heights, Ohio, skjerpet oppgaven begrepet kompleksitet og definerte en måte å karakterisere de vanskeligste problemene i NP. Det beviste, i et glimt av algoritmisk alkymi, at ett problem, kjent som tilfredshetsproblemet (søke en løsning for en formel gitt et sett med begrensninger), på en måte var det vanskeligste problemet i NP, og at alle de andre NP-problemene kunne reduseres til det.

Dette var et avgjørende teorem: Hvis det er en polynom-tidsalgoritme som løser tilfredshetsproblemet, vil den algoritmen tjene som en skjelettnøkkel, og låse opp løsninger på alle problemene i NP. Og hvis det finnes en polynom-tidsløsning for alle problemene i NP, så er P = NP.

Blant informatikere er Cooks teorem ikonisk. Leslie Valiant, fra Harvard, husket på symposiet i 2019 nøyaktig hvor og når han først hørte om det. Etter å ha fullført grunnstudier i matematikk, hadde han begynt på en doktorgrad i informatikk. Selv om det var kurs og grader i dette nye feltet, sa han, føltes det flyktig, kanskje manglet dypt intellektuelt innhold. Det var en alvorlig bekymring for folk som drev med informatikk på den tiden, sa han. De spurte: ‘Er dette en åker? Hvor går det?’ En dag kom Valiant over Cooks avis. Han leste den over natten. Jeg ble forvandlet, sa han. På et øyeblikk ble mine bekymringer for informatikk veldig redusert. Dette papiret – for meg gjorde det virkelig feltet. Jeg tror det gjorde informatikk - gjorde det til noe av substans.

Og så, som historien sier, etter Cooks teorem kom en syndflod.

I 1972 demonstrerte Dick Karp, en dataforsker ved Berkeley, etter å ha lest Cooks esoteriske artikkel, at mange av de klassiske beregningsproblemene som han var nært kjent med - i hovedsak alle problemer han ikke visste hvordan han skulle løse, hentet fra matematisk programmering, operasjonsforskning, grafteori, kombinatorikk og beregningslogikk – hadde den samme transformasjonsegenskapen som Cook hadde funnet med tilfredshetsproblemet. Totalt fant Karp 21 problemer, inkludert ryggsekkproblemet (som leter etter den optimale måten å pakke en begrenset plass med de mest verdifulle gjenstandene), problemet med den reisende selgeren (å finne kortest mulig rute som besøker hver by én gang og returnerer til byen av opprinnelse), og Steiner-treproblemet (som søker å koble et sett med punkter optimalt med linjestykker med minimum total lengde).

Karp viste at denne spesielle samlingen av problemer alle var likeverdige, noe som igjen viste at mønsteret identifisert av Cook ikke var et isolert fenomen, men snarere en klassifiseringsmetodikk for overraskende kraft og rekkevidde. Det var en slags lakmustest, som identifiserte klassen av det som ble kjent som NP-komplette problemer: en løsning på noen ville knekke dem alle.

Papadimitriou tenker på NP-fullstendighet som et allsidig verktøy. Hvis du ikke kan løse et problem, prøv å bevise at det er NP-komplett, for dette vil kanskje spare deg for mye tid, sa han på det offentlige foredraget - du kan gi opp en eksakt løsning og gå videre til å løse en tilnærming eller variasjon av problemet i stedet.

I historiens store fei ser Papadimitriou fenomenet NP-fullstendighet og P vs. NP-oppdraget som datavitenskapens skjebne. For som vitenskapelig serendipitet ville ha det, konvergerte en sovjetisk matematiker, Leonid Levin, et resultat tilsvarende Cooks på mer eller mindre samme tid. Levin, nå ved Boston University, gjorde arbeidet sitt bak jernteppet. Etter at det fikk større oppmerksomhet (han immigrerte til Amerika i 1978), ble resultatet kjent som Cook-Levin-teoremet.

Og i en ytterligere coda et tiår eller så senere, ble et tapt brev oppdaget i Princeton-arkivene til den østerrikske logikeren Kurt Gödel. I 1956 hadde han skrevet til von Neumann og spurt om et logisk problem - som i moderne språkbruk ville bli kalt NP-komplett - kunne løses i polynomisk tid. Han mente at dette ville få konsekvenser av største omfang.

Klikkeproblemet: Søk etter klikker i en graf, for eksempel en viss undergruppe av venner i et sosialt nettverk.

DEREK BRAHNEY

Fire. Selv om et halvt århundres arbeid ikke har gitt noe i nærheten av en løsning, fanger noen resultater i det minste fantasien: et papir i 2004 hevdet et bevis for P = NP ved å bruke såpebobler som en mekanisme for analog beregning (såpefilm, naturligvis innretting i minimumsenergikonfigurasjonen, løser det NP-komplette Steiner-treproblemet på en måte).

I disse dager er det en sjelden fugl av en dataforsker – for eksempel Ron Fagin, en IBM-stipendiat – som takler problemet på strak arm. På 1970-tallet produserte han Fagins teorem, som karakteriserte klassen NP når det gjelder matematisk logikk. Og han har løst problemet mer enn én gang, men resultatene varte aldri mer enn noen få dager før han fant en feil. Fagin fikk nylig midler til et P vs. NP-prosjekt fra IBMs Exploratory Challenges-program som støtter eventyrlig forskning. Når han forklarer hvorfor han holder på, siterer han gjerne Theodore Roosevelt, som sa at det er langt bedre å våge mektige ting enn å rangere blant dem som lever i en grå skumring som verken kjenner seier eller nederlag.

Men de fleste kompleksitetsteoretikere drømmer litt mindre, og velger i stedet for indirekte tilnærminger – vippe problemet, omforme eller omforme det, utforske relaterte omgivelser og ytterligere kutte ned arsenalet av verktøy som kan brukes mot det (mange er nå kjent for å være ubrukelig ).

Ryan Williams, en informatiker ved MIT, prøver å belyse problemet både ovenfra og nedenfra – undersøker naturen til øvre og nedre grenser på kjerneberegningsproblemer. En øvre grense, enkelt sagt, er en spesifikk matematisk påstand om at det eksisterer en konkret algoritme som løser et bestemt problem uten å overskride en viss mengde ressurser (tid, minne, energi). En nedre grense er det immaterielle motsatte: det er en generell påstand om umulighet, som viser at ingen slik algoritme eksisterer universelt. Et fokus for Williams forskning er å gjøre nedre grenser konstruktive og konkrete - matematiske objekter med beskrivbare trekk. Han mener at mer konstruktive tilnærminger til nedre grenser er nettopp det vi mangler fra dagens tilnærminger innen kompleksitetsteori.

Williams har satt sannsynligheten for at P ≠ NP til ganske moderate 80 %. Men i det siste uttrykker noen forskere på feltet tvil om selv det nivået av sikkerhet. Mer og mer begynner jeg å lure på om P er lik NP, sier Toniann Pitassi, en dataforsker ved University of Toronto og en tidligere doktorgradsstudent ved Cook's. Hennes tilnærming til å sirkle rundt problemet er å studere både oppskalerte og nedskalerte analoger, hardere og enklere modeller. Noen ganger blir det klarere å generalisere spørsmålet, sier hun. Men totalt sett har hun ikke oppnådd klarhet: De fleste tror P ikke er lik NP. og jeg vet ikke. Kanskje det bare er meg, men jeg føler at det har blitt mindre og mindre klart at det er sannheten.

Historisk, påpeker Pitassi, har overraskende resultater tidvis kommet ut av ingensteds – tilsynelatende umuligheter som har vist seg mulig av smarte algoritmedesignere. Det samme kan skje med P vs. NP, kanskje om 50 år eller et århundre til. Et av de viktigste resultatene i hele kompleksitetsteorien ble for eksempel oppnådd av David Barrington, ved University of Massachusetts, Amherst, i 1989. Hovedpoenget (for våre formål) er at han utviklet en smart algoritme, som satset på å gjøre noe som tilsynelatende burde ha krevd en ubegrenset mengde minne, men som faktisk brukte en forbløffende liten mengde – bare fem biter med informasjon, nok til å spesifisere et tall mellom én og 32 (inklusive) eller et ord på to bokstaver.

Et nyere og relatert resultat, fra 2014, overrasket James Cook. Med utgangspunkt i Barringtons teorem bruker den minnet på en fantastisk merkelig måte. Som antydet i tittelen på artikkelen, av University of Amsterdams Harry Buhrman og samarbeidspartnere, handler det om databehandling med fullt minne. James kan skrangle av avisens innledende avsnitt praktisk talt ordrett:

Se for deg følgende scenario. Du ønsker å utføre en beregning som krever mer minne enn du har tilgjengelig på datamaskinen. En måte å håndtere dette problemet på er å installere en ny harddisk. Det viser seg at du har en harddisk, men den er full av data, bilder, filmer, filer osv. Du trenger ikke å få tilgang til disse dataene for øyeblikket, men du vil heller ikke slette dem. Kan du bruke harddisken til beregningen, eventuelt endre innholdet midlertidig, og garantere at når beregningen er fullført, er harddisken tilbake i sin opprinnelige tilstand med alle data intakt?

Svaret, kontraintuitivt, er ja.

James tenker på det som et lånt minne. Etter at sjokket av dette resultatet sank inn, hadde han det moro med å finne ut hvordan han skulle bruke det på et bestemt problem – å fortsette der faren hans slapp.

For et par tiår siden gikk Steve Cook videre til andre relaterte problemer innen kompleksitetsteori. Med ett problem kom han med en formodning om hvor mye minne en algoritme ville trenge for å løse problemet – å finpusse det til et absolutt minimum. I 2019 implementerte James, sammen med Ian Mertz, en av Pitassis PhD-studenter, den poetiske ideen om å låne minne og beviste at enda mindre minne var nødvendig. Resultatet gikk ikke hele veien til å tilbakevise farens formodning, men det er likevel et lite fremskritt i det store kompleksitetsoppdraget.

Og problemer i kompleksitetsteori, observerer James, har noen ganger en dominoeffekt - hvis det er et bevis i et kritisk hjørne, så faller alle dominobrikkene. Gjennombruddsresultatene, de viktigste, kommer fra en lang rekke med arbeid, utført av mange forskjellige mennesker, som gjør gradvis fremgang og etablerer sammenhenger mellom ulike spørsmål, inntil det endelig dukker opp et stort resultat.

Han nevner også en advarsel: mens en virkelig djevelsk rask P = NP-algoritme ville være verdensomspennende, er det også et scenario der P = NP kan være en skuffelse. Det kan vise seg at en P-algoritme som er i stand til å løse det NP-komplette problemet er på en tidsskala på for eksempel, n ^100. Teknisk sett faller det under P: det er et polynom, sier James. Men n ^100 er fortsatt veldig upraktisk - det vil bety at eventuelle betydelige problemer fortsatt vil være utenfor rekkevidde på menneskelig tidsskala.

Det er selvfølgelig forutsatt at vi kan finne algoritmen i utgangspunktet. Donald Knuth, en algoritmist ved Stanford, har de siste årene ombestemt seg - han snudde litt. Hans intuisjon er at P faktisk er lik NP, men at vi sannsynligvis aldri vil være i stand til å bruke det faktum, praktisk talt - fordi vi faktisk ikke vet noen av algoritmene som tilfeldigvis fungerer. Det er forbløffende antall algoritmer der ute, forklarer han, men de fleste av dem er utenfor vår kunnskap. Så mens noen forskere kan insistere på at ingen P = NP-algoritme eksisterer, hevder Knuth at det er mer sannsynlig at ingen polynom-tidsalgoritme noen gang vil bli legemliggjort - faktisk skrevet ned som et program - av bare dødelige.

For Papadimitriou ville ethvert svar slukke en livslang besettelse. Han mener P vs. NP-problemet hører hjemme i riket av grunnleggende vitenskapelige gåter som livets opprinnelse og foreningen av naturens kraftfelt. Det er den typen dyptgående, konsekvent puslespill, konkret, men likevel universelt, sa han, som gir mening ikke bare til vitenskapen, men til menneskelivet selv.

Tenk deg at vi er heldige, og vi er i stand til å presse ytterligere et par tusen år ut av denne planeten, mot oddsen og til tross for rart, sa han. Og vi løser ikke disse problemene. Hva er poenget?!