Det 50-åriga problemet som undviker teoretisk datavetenskap

En lösning på P vs NP kan låsa upp otaliga beräkningsproblem – eller hålla dem utom räckhåll för alltid.

Steinerträdets problem: Anslut en uppsättning punkter med linjesegment med minsta totala längd. Derek Brahney

förbi

• Siobhan Roberts arkivsida

27 oktober 2021

ett. Måndagen den 19 juli 2021, mitt under ännu en märklig pandemisommar, twittrade en ledande datavetare inom området komplexitetsteori ut ett public service-meddelande om ett administrativt fel i en tidskrift. Han kvitterade med en mycket laddad

Lycklig måndag.

Den här historien var en del av vårt novembernummer 2021

• Se resten av frågan
• Prenumerera

I ett parallellt universum hade det kanske varit en väldigt glad måndag. Ett bevis hade dykt upp online på den uppskattade tidskriften ACM Transactions on Computational Theory, som handlar med enastående originalforskning som utforskar gränserna för genomförbar beräkning. Resultatet påstods lösa problemet med alla problem - den teoretiska datavetenskapens heliga gral, värd ett pris på 1 miljon dollar och berömmelse som konkurrerar med Aristoteles för alltid.

Detta värdefulla problem – känt som P kontra NP – anses på en gång vara det viktigaste inom teoretisk datavetenskap och matematik och helt utom räckhåll. Den tar upp frågor som är centrala för beräkningens löfte, gränser och ambitioner, och frågar:

Varför är vissa problem svårare än andra?

Vilka problem kan datorer lösa realistiskt?

Hur lång tid kommer det att ta?

Och det är ett uppdrag med stora filosofiska och praktiska vinster.

Titta, den här P kontra NP-frågan, vad kan jag säga? Scott Aaronson, en datavetare vid University of Texas i Austin, skrev i sin memoarer av idéer , Kvantberäkning sedan Demokrit . Folk gillar att beskriva det som 'förmodligen det centrala olösta problemet med teoretisk datavetenskap.' Det är en komisk underdrift. P vs NP är en av de djupaste frågorna som människor någonsin har ställt.

Ett sätt att tänka på den här historiens huvudpersoner är följande:

P representerar problem som en dator lätt kan lösa.

NP representerar problem som, när de är lösta, är lätta att kontrollera – som pussel eller Sudoku. Många NP-problem motsvarar några av de mest envisa och akuta problem som samhället står inför.

Miljonfrågan som ställs av P vs. NP är denna: Är dessa två klasser av problem en och samma? Det vill säga, skulle de problem som verkar så svåra faktiskt kunna lösas med en algoritm inom rimlig tid, om bara den rätta, djävulskt snabba algoritmen kunde hittas? Om så är fallet är många svåra problem plötsligt lösbara. Och deras algoritmiska lösningar skulle kunna åstadkomma samhällsförändringar av utopiska proportioner – inom medicin och teknik och ekonomi, biologi och ekologi, neurovetenskap och samhällsvetenskap, industri, konst, till och med politik och vidare.

Ibland utvecklas klassificeringarna – svåra problem visar sig vara lätta när forskare hittar mer effektiva lösningar. Att testa om ett tal är primtal har till exempel varit känt för att vara i klassen NP sedan mitten av 1970-talet. Men 2002 tog tre datavetare vid Indian Institute of Technology Kanpur fram ett ovillkorligt bevis och en smart algoritm som slutligen bekräftade att problemet också fanns i P.

Om Allt de knepiga problemen skulle kunna omvandlas med ett sådant algoritmiskt grepp, konsekvenserna för samhället – för mänskligheten och vår planet – skulle bli enorma.

Till att börja med skulle krypteringssystem, varav de flesta är baserade på NP-problem, vara knäckta. Vi måste hitta ett helt annat sätt att skicka säker kommunikation. Proteinveckning, en 50-årig stor utmaning inom biologin, skulle bli mer lätthanterlig och låsa upp nyfunna förmågor att designa läkemedel som botar eller behandlar sjukdomar och upptäcker enzymer som bryter ner industriavfall. Det skulle också innebära att hitta optimala lösningar på vardagliga svåra problem, som att kartlägga en roadtrip för att nå alla destinationer med minimalt med bilkörning, eller sitta bröllopsgäster så att bara vänner delar samma middagsbord.

Sedan P vs. NP-problemet uppstod för 50 år sedan – som uppstod från den betydelsefulla skärningspunkten mellan matematisk logik och elektronisk datorteknik – har forskare runt om i världen gjort herkuliska försök till en lösning. Vissa datavetare har föreslagit att ansträngningarna kan liknas bättre vid Sisyfos, som arbetade utan upplösning. Men medan de som först utforskade problemet har ont om tid för att hitta en lösning, tar de nyare generationerna glatt upp uppdraget.

För Manuel Sabin, en datavetare som precis avslutat en doktorsexamen vid UC Berkeley, ligger lockelsen i att undersöka omöjligheten av problem där du inte kommer att veta svaret förrän solen slukar jorden. Sökandet kan vara quixotiskt, men Sabin skulle ångra att han inte lutade vid dessa väderkvarnar.

Timothy Gowers, en matematiker vid University of Cambridge, kallar det en av mina personliga matematiska sjukdomar. Han förlorade sommaren 2013 till jakten, efter att han bad eleverna om en uppsats om ämnet på ett prov. Som han berättade på sin blogg: Efter att ha markerat uppsatserna i juni tänkte jag att jag bara skulle spendera en timme eller två på att tänka på problemet igen, och den där timmen eller två förvandlades av misstag till ungefär tre månader.

Problemet med den resande säljaren: Hitta den kortaste möjliga vägen som besöker varje stad en gång, och i slutändan återvända till ursprungsstaden.

DEREK BRAHNEY

Uppdraget har till och med stört University of Torontos datavetare Stephen Cook, som inramade problemet och lanserade fältet beräkningskomplexitet med en nyskapande uppsats 1971. För detta arbete vann han Turing Award, datavetenskapens motsvarighet till Nobelpriset. Men han har inte lyckats hitta en lösning. Cook säger att han aldrig haft några bra idéer – det är bara för svårt.

två. Michael Sipser, en datavetare vid MIT, uppskattar att han har spenderat, allt som sagt, så mycket som ett decennium på problemet. Han blev intresserad under gymnasiet på 1970-talet, och han satsade sin studiekamrat Len Adleman ett uns guld att det skulle vara löst i slutet av århundradet (Sipser betalade).

På 1980-talet uppnådde han ett bra resultat genom att lösa en version av problemet med en begränsad beräkningsmodell – vilket ledde till en spännande period på fältet med flera vackra resultat, vilket gav anledning till hopp om att en lösning kanske inte är för långt borta.

Sipser återkommer fortfarande till problemet då och då, och han är en ståndaktig ambassadör som håller otaliga föredrag i ämnet.

Sättet han går in på en tillgänglig förklaring av P vs. NP är med ett grundläggande multiplikationsproblem: 7 × 13 = ?

Svaret, 91, är lätt nog att beräkna i ditt huvud. Även om det inte är lika lätt att multiplicera större siffror, skulle det fortfarande ta en dator praktiskt taget ingen tid alls.

Men att vända på dessa problem är en annan sak. Tänk till exempel att hitta de två 97-siffriga primtalen som multipliceras för att producera detta mycket stora tal:

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

Detta factoringproblem var en del av en utmaning att bedöma svårigheten att knäcka RSA-nycklarna som används i kryptografi. Att lösa det tog 80 processorer fem månaders kontinuerlig datoranvändning, förklarar Sipser – vilket tar ungefär 33 år med bara en enda processor. Factoring är ett svårt problem eftersom alla nuvarande metoder söker svaret via brute force, kontrollerar det astronomiska antalet möjligheter en efter en. Även för en dator är detta en långsam process.

Den intressanta frågan här är, behöver du verkligen söka? säger Sipser. Eller finns det något sätt att lösa factoringproblemet som zoomar in på svaret snabbt utan att söka? Vi vet inte svaret på den frågan.

Frågor som denna hamnar i hjärtat av beräkningskomplexitet - ett fält fullt av djuriska problem som forskare försöker förstå. Aaronson har sammanställt en Complexity Zoo, en onlinekatalog med 545 klasser av problem (och räknas). Var och en klassificeras efter dess komplexitet, eller svårighetsgrad, och de resurser – tid, minne, energi – som krävs för att hitta lösningar. P och NP är huvudattraktionerna.

Som vetenskaplig serendipity ville ha det, konvergerade en sovjetisk matematiker, Leonid Levin, till ett resultat som motsvarar Cooks vid ungefär samma tidpunkt.

P är klassen som startade det hela. Det är den klass av problem som kan lösas av en dator inom rimlig tid. Mer specifikt är P-problem sådana där tiden det tar att hitta en lösning kan beskrivas av en polynomfunktion, som t.ex. n ^2. I polynomtidsalgoritmer, n är storleken på insatsen, och tillväxt mot den insatsen sker i en rimlig takt (i det här fallet till två).

Däremot kanske vissa svåra NP-problem bara kan lösas med algoritmer med körtider definierade av en exponentiell funktion, såsom 2^n - vilket ger en exponentiell tillväxthastighet (som med spridningen av covid). NP, som Aaronson beskriver det, är klassen av brustna förhoppningar och lediga drömmar. Han är dock snabb med att klargöra en vanlig missuppfattning: alla NP-problem är inte svåra. Klassen NP innehåller faktiskt klassen P — för problem med enkla lösningar är naturligtvis också lätta att kontrollera.

NP:s mer utmanande problem har ofta betydelsefulla praktiska tillämpningar. För dessa problem skulle en uttömmande brute-force-sökning efter en lösning sannolikt pågå under en opraktisk lång tid - geologisk tid - innan ett svar produceras. Om en brute-force sökalgoritm är den bästa möjliga algoritmen, är P inte lika med NP.

Och bland cognoscenti är det tydligen konsensus, som vissa liknar mer vid religiös tro: P ≠ NP. De flesta tillåter bara en bit hopp om att motsatsen ska visa sig sann. Jag skulle ge det en 2 till 3% chans att P är lika med NP, säger Aaronson. Det är oddsen jag skulle ta.

Resultatet som publicerades i juli presenterade ett bevis på exakt det långskottet. Men det var bara det senaste i en lång tradition av bevis som inte går igenom. Inom en dag efter publicering, i en omgång av händelser värdig Monty Python, togs tidningen bort från online-tidskriften; sedan verkade den dyka upp igen en kort stund innan den försvann permanent. Det var den senaste versionen av en artikel som författaren hade postat mer än 60 gånger på arXiv förtrycksserver under det senaste decenniet. Tidskriftens chefredaktör förklarade på Twitter att resultatet hade förkastats, men i ett fall av mänskliga misstag hade tidningens läggning på något sätt förändrats från avslag till accepterande och beviset hade hittat sin väg till publicering.

3. I början av augusti, när jag träffade Steve Cook på hans kontor på campus, hade han varken sett eller hört talas om det senaste P vs. NP-beviset. Nu 81, hade han nyligen gått i pension, eftersom hans minne sviktade. Det är därför vi har James här, sa han - hans son James, 36, också en datavetare, hade följt med oss ​​för mitt besök. Steve var mitt uppe i att rensa ut sitt kontor. En gigantisk återvinningskärl stod mitt i rummet och fylldes med gamla gulnande nummer av Journal of Symbolic Logic, en hög med superfeta telefonböcker från Toronto som väntade i närheten.

Under åren har Cook sett många bevis som påstår sig lösa P vs. NP-problemet. År 2000, efter att Clay Mathematics Institute utnämnde det till ett av de sju olösta millennieproblemen (vart och ett värt ett pris på 1 miljon dollar), översvämmades han av meddelanden från människor som trodde att de hade segrat. Alla resultat var felaktiga, om inte uppenbart falska. Ungefär hälften påstod sig ha bevisat att P är lika med NP; den andra halvan gick åt motsatt håll. För inte så länge sedan påstod en person ha bevisat båda.

Cook, i sin uppsats från 1971, gissade att P inte är lika med NP (han formulerade det med en annan terminologi som var vanlig vid den tiden). Han har sedan dess investerat en betydande om än obestämd tid för att fastställa att så är fallet. Jag har inget bra minne av att slita, säger han, men hans kollegor minns att när de gick in på avdelningen på helgen var Steve där på sitt kontor.

Såvida han inte kappseglar segelbåtar, är Cook inte en som har bråttom; han gillar att ge en idé tid. Och hans tidigare elever minns en tydlig brist på svindlande. Datavetaren Anna Lubiw, vid University of Waterloo, säger att när han undervisade i Cooks teorem – en del av den banbrytande uppsatsen – hänvisade han aldrig till det som sådant och gav aldrig ens några antydningar om att det var han som bevisade det. Maria Klawe, en matematiker och datavetare och ordförande för Harvey Mudd College, säger att hon regelbundet skulle rätta Cook när han gick vilse och lärde ut bevis på att han visste utan och innan: Han skulle fastna och säga: 'Okej. Berätta för mig hur bevisen går.’ Cook var också känd blygsam i anslagsansökningar och rapporter rörande hans forskning – han skulle erkänna: Ärligt talat, jag har gjort små framsteg …

Relaterad berättelse

Datavetenskapens utveckling Att beräkna energinivåerna för en heliumatom 1958 var betydligt svårare än det är idag. Men en jämförelse av då och nu metoder avslöjar några kontraintuitiva anomalier om inverkan av datavetenskap.

Han gjorde dock framsteg med att rekrytera James för att ta upp saken. Tidigt visade James ett intresse för matematik och datoranvändning - vid nio års ålder uppmanade han sin pappa att lära honom boolesk algebra och logik. För ett par år sedan, efter att ha tagit en doktorsexamen vid Berkeley och gjort en snålhet på Google, började han som en oberoende forskare med fokus på diverse projekt, några av dem indirekt kopplade till P vs. NP. Och trots meritlistan är James, som har en slående likhet med sin far, oförskämd över att ha ärvt ett sådant till synes oändligt uppdrag. Han betraktar det som han skulle göra varje matematisk strävan: det är ett roligt pussel. Det måste finnas svar på de här frågorna, säger han. Och det är som, kom igen, någon måste lösa det. Låt oss bara ta reda på det här. Det var längesedan. Det är pinsamt att vi inte vet svaret ännu.

Bristen på framsteg har inte hindrat denna gemenskap av glada sisyfer från att fira beräkningskomplexitetens 50-årsjubileum. Festligheterna började 2019, när anhängare från hela världen samlades vid Fields Institute for Research in Mathematical Sciences, vid University of Toronto, för ett symposium till Cooks ära. Christos Papadimitriou, en datavetare vid Columbia University som har tillbringat en stor del av sin karriär med att arbeta med P vs. NP, inledde evenemanget med en offentlig föreläsning, som ser tillbaka inte ett halvt sekel utan årtusenden.

Han började med att beskriva urgamla uppdrag efter lösningar – med hjälp av algebraiska verktyg eller rätsida och kompass, som han ansåg som rudimentära beräkningsformer. Papadimitrious berättelse kom så småningom fram till Alan Turing, den brittiske matematikern vars uppsats från 1936 On Computable Numbers formaliserade begreppen algoritm och beräkning. Turing visade också – med sin idé om en universell datormaskin – att det inte finns något mekaniskt sätt (det vill säga utfört av en maskin) att bevisa sanningen eller falskheten i matematiska påståenden; inget systematiskt sätt att skilja det bevisbara från det obevisbara.

Papadimitriou sa att han anser att Turings papper är datavetenskapens födelseattest - och födelseattesten säger att datavetenskap föddes med en skarp förståelse för sina egna begränsningar. Han ansåg att datavetenskap är det enda kända fältet för vetenskaplig diskurs som föddes med en sådan medvetenhet - till skillnad från andra vetenskaper, som förstår sina egna begränsningar, som resten av oss, i slutet av medelåldern.

Det dröjde inte länge efter att Turings idéer (och liknande idéer från andra) hittats i de första datorerna som forskare konfronterade frågor om maskinernas inneboende kapacitet och begränsningar. I början av 1950-talet skröt John von Neumann, den ungersk-amerikanske pionjären inom den moderna datorn, om en algoritm som visar att han är polynom, jämfört med den exponentiella operatören, som Papadimitriou påminde om – han hade överlistat en långsam algoritm med en snabb. Detta var början till en ny teori: beräkningskomplexitetsteori. Kärnan i det var att endast polynomalgoritmer i någon mening är bra eller praktiska eller värda att sikta på ett problem, medan en exponentiell algoritm, sa Papadimitriou, är den algoritmiska motsvarigheten till döden.

Cook började tänka på komplexitet i mitten av 1960-talet. Medan han arbetade på sin doktorsexamen vid Harvard funderade han på om det är möjligt att bevisa, givet vissa beräkningsmodeller, att multiplikation är svårare än addition (det är fortfarande ett öppet problem).

1967, enligt en bok om Cook som kommer från Association for Computing Machinery (ACM), medan han var postdoc vid Berkeley, skrev han kursanteckningar som innehöll fröet till hans stora resultat. Han hade utarbetat en formulering av komplexitetsklasserna som kom att kallas P och NP, och han ställde frågan om P var lika med NP. (Vid ungefär samma tid cirklade andra, inklusive datavetaren Jack Edmonds, nu pensionerad från University of Waterloo, kring samma idéer.)

Men datavetenskapens område hade bara börjat, och för de flesta vetenskapsmän och matematiker var sådana idéer obekanta om inte direkt konstiga. Efter fyra år på Berkeleys matematikavdelning övervägdes Cook för anställning men erbjöds inte en position. Han hade förespråkare vid universitetets nya institution för datavetenskap, och de lobbade för att han skulle få en plats i deras led, men dekanen var inte benägen att ge någon som de berömda matematikerna hade förnekat.

De flesta komplexitetsteoretiker drömmer lite mindre och väljer istället indirekta tillvägagångssätt.

1970 flyttade Cook till University of Toronto. Året därpå publicerade han sitt genombrott. Inlämnad till ett symposium av ACM som hölls i maj i Shaker Heights, Ohio, skärpte tidningen begreppet komplexitet och definierade ett sätt att karakterisera de svåraste problemen i NP. Det bevisade, i en blixt av algoritmisk alkemi, att ett problem, känt som tillfredsställbarhetsproblemet (att söka en lösning för en formel med en uppsättning begränsningar), på sätt och vis var det svåraste problemet i NP, och att alla andra NP-problem skulle kunna reduceras till det.

Detta var ett avgörande teorem: om det finns en polynom-tidsalgoritm som löser tillfredsställbarhetsproblemet, då kommer den algoritmen att fungera som en skelettnyckel och låsa upp lösningar på alla problem i NP. Och om det finns en polynom-tidslösning för alla problem i NP, så är P = NP.

Bland datavetare är Cooks teorem ikonisk. Leslie Valiant, från Harvard, mindes vid symposiet 2019 exakt var och när han först hörde talas om det. Efter att ha avslutat grundutbildningen i matematik, hade han påbörjat en doktorsexamen i datavetenskap. Även om det fanns kurser och examina inom detta spirande område, sa han, kändes det tillfälligt, kanske saknade det djupt intellektuellt innehåll. Det var ett allvarligt bekymmer för människor som ägnade sig åt datavetenskap vid den tiden, sa han. De frågade: ’Är det här en åker? Vart är det på väg?’ En dag kom Valiant på Cooks tidning. Han läste den över en natt. Jag förvandlades, sa han. På ett ögonblick minskade min oro för datavetenskap väldigt mycket. Det här papper - för mig gjorde det verkligen fältet. Jag tror att det gjorde datavetenskap – gjorde det till något väsentligt.

Och sedan, som historien säger, efter Cooks teorem kom en syndaflod.

1972 visade Dick Karp, en datavetare vid Berkeley, efter att ha läst Cooks esoteriska artikel, att många av de klassiska beräkningsproblem som han var nära förtrogen med - i princip varje problem han inte visste hur han skulle lösa, hämtade från matematisk programmering, operationsforskning, grafteori, kombinatorik och beräkningslogik – ägde samma transformationsegenskap som Cook hade funnit med tillfredsställbarhetsproblemet. Totalt hittade Karp 21 problem, inklusive ryggsäcksproblemet (som letade efter det optimala sättet att packa ett begränsat utrymme med de mest värdefulla föremålen), problemet med resande säljare (att hitta den kortaste möjliga vägen som besöker varje stad en gång och återvänder till staden ursprung) och Steiner-trädproblemet (som söker att optimalt koppla samman en uppsättning punkter med linjesegment med minsta totala längd).

Karp visade att denna speciella samling av problem alla var likvärdiga, vilket i sin tur visade att mönstret som identifierats av Cook inte var ett isolerat fenomen, utan snarare en klassificeringsmetodik för överraskande makt och räckvidd. Det var ett slags lackmustest, som identifierade klassen för vad som blev känt som NP-kompletta problem: en lösning på alla skulle knäcka dem alla.

Papadimitriou tänker på NP-fullständighet som ett mångsidigt verktyg. Om du inte kan lösa ett problem, försök att bevisa att det är NP-komplett, för det här kanske kommer att spara dig mycket tid, sa han vid den offentliga föreläsningen — du kan ge upp en exakt lösning och gå vidare till att lösa en approximation eller variation av problemet istället.

I historiens storslagna svep ser Papadimitriou fenomenet NP-fullständighet och P vs. NP-uppdraget som datavetenskapens öde. För som vetenskaplig serendipity skulle ha det, konvergerade en sovjetisk matematiker, Leonid Levin, till ett resultat som motsvarar Cooks mer eller mindre samtidigt. Levin, nu vid Boston University, gjorde sitt arbete bakom järnridån. Efter att det fått bredare uppmärksamhet (han immigrerade till Amerika 1978) blev resultatet känt som Cook-Levin-satsen.

Och i ytterligare en coda ett decennium senare upptäcktes ett förlorat brev i Princeton-arkivet av den österrikiske logikern Kurt Gödel. 1956 skrev han till von Neumann och frågade om ett logiskt problem – som i modernt språkbruk skulle kallas NP-komplett – kunde lösas i polynomtid. Han menade att detta skulle få konsekvenser av största omfattning.

Klickproblemet: Sök efter klick i en graf, till exempel en viss undergrupp av vänner i ett socialt nätverk.

DEREK BRAHNEY

Fyra. Även om ett halvt sekels arbete inte har gett något i närheten av en lösning, fångar vissa resultat åtminstone fantasin: ett papper 2004 hävdade ett bevis för P = NP med hjälp av såpbubblor som en mekanism för analog beräkning (såpfilm, naturligtvis anpassning i minimienergikonfigurationen löser det NP-kompletta Steinerträdproblemet på ett sätt).

Nuförtiden är det en sällsynt fågel av en datavetare – till exempel Ron Fagin, en IBM-stipendiat – som tar itu med problemet direkt. På 1970-talet producerade han Fagins teorem, som karakteriserade klassen NP i termer av matematisk logik. Och han har löst problemet mer än en gång, men resultaten stod aldrig i mer än några dagar innan han hittade en bugg. Fagin fick nyligen finansiering för ett P vs. NP-projekt från IBM:s Exploratory Challenges-program som stödjer äventyrlig forskning. När han förklarar varför han håller på, citerar han gärna Theodore Roosevelt, som sa att det är mycket bättre att våga mäktiga saker än att rankas bland dem som lever i en grå skymning som varken känner till seger eller nederlag.

Men de flesta komplexitetsteoretiker drömmer lite mindre och väljer istället indirekta tillvägagångssätt – luta problemet, omforma eller omforma det, utforska relaterade miljöer och ytterligare skära ner arsenalen av verktyg som skulle kunna användas mot det (många är nu kända för att vara värdelösa ).

Ryan Williams, en datavetare vid MIT, försöker belysa problemet både ovanifrån och underifrån – undersöker karaktären hos övre och nedre gränser för grundläggande beräkningsproblem. En övre gräns, enkelt uttryckt, är ett specifikt matematiskt påstående att det finns en konkret algoritm som löser ett visst problem utan att överskrida en viss mängd resurser (tid, minne, energi). En nedre gräns är den immateriella motsatsen: det är ett allmänt påstående om omöjlighet, som visar att ingen sådan algoritm existerar universellt. Ett fokus för Williams forskning är att göra lägre gränser konstruktiva och konkreta - matematiska objekt med beskrivbara egenskaper. Han menar att mer konstruktiva förhållningssätt till lägre gränser är just vad vi saknar från nuvarande förhållningssätt inom komplexitetsteorin.

Williams har fastställt sannolikheten att P ≠ NP till ganska måttliga 80 %. Men på senare tid uttrycker vissa forskare inom området tvivel om även den nivån av säkerhet. Mer och mer börjar jag undra om P är lika med NP, säger Toniann Pitassi, en datavetare vid University of Toronto och en före detta doktorand vid Cook's. Hennes sätt att cirkla runt problemet är att studera både uppskalade och nedskalade analoger, hårdare och enklare modeller. Att generalisera frågan ibland gör det tydligare, säger hon. Men totalt sett har hon inte uppnått klarhet: De flesta tror att P inte är lika med NP. Och jag vet inte. Kanske är det bara jag, men jag känner att det har blivit mindre och mindre tydligt att det är sanningen.

Historiskt, påpekar Pitassi, har överraskande resultat emellanåt kommit från ingenstans – till synes omöjligheter som visat sig vara möjliga av smarta algoritmdesigners. Samma sak kan hända med P vs. NP, kanske om ytterligare 50 år eller ett sekel. Ett av de viktigaste resultaten inom all komplexitetsteori, till exempel, uppnåddes av David Barrington, från University of Massachusetts, Amherst, 1989. Kontentan av det (för våra syften) är att han tog fram en smart algoritm, som satsade på att göra något som till synes skulle ha krävt en obegränsad mängd minne men som faktiskt använt en förvånansvärt liten mängd - bara fem bitar information, tillräckligt för att ange ett tal mellan ett och 32 (inklusive) eller ett tvåbokstavsord.

Ett nyare och relaterat resultat, från 2014, överraskade James Cook. Utifrån Barringtons teorem använder den minnet på ett underbart konstigt sätt. Som antyds i titeln på tidningen, av University of Amsterdams Harry Buhrman och medarbetare, handlar det om datorer med fullt minne. James kan skramla av tidningens inledande stycke praktiskt taget ordagrant:

Föreställ dig följande scenario. Du vill utföra en beräkning som kräver mer minne än vad du för närvarande har tillgängligt på din dator. Ett sätt att hantera detta problem är att installera en ny hårddisk. Som det visar sig har du en hårddisk men den är full med data, bilder, filmer, filer etc. Du behöver inte komma åt den informationen för tillfället men du vill inte heller radera den. Kan du använda hårddisken för din beräkning, eventuellt ändra dess innehåll tillfälligt, och garantera att när beräkningen är klar är hårddisken tillbaka i sitt ursprungliga tillstånd med all data intakt?

Svaret, kontraintuitivt, är ja.

James ser det som ett lånat minne. Efter att chocken av detta resultat sjönk in, hade han roligt med att komma på hur han skulle tillämpa det på ett visst problem – att fortsätta där hans pappa slutade.

För ett par decennier sedan gick Steve Cook vidare till andra relaterade problem inom komplexitetsteorin. Med ett problem gjorde han en gissning om hur mycket minne som en algoritm skulle behöva för att lösa problemet – finslipa det till ett absolut minimum. Under 2019 använde James, tillsammans med Ian Mertz, en av Pitassis doktorander, den poetiska idén att låna minne och bevisade att ännu mindre minne behövdes. Resultatet gick inte hela vägen till att motbevisa hans pappas gissningar, men det är ändå lite framsteg i den stora komplexitetssträvan.

Och problem i komplexitetsteorin, observerar James, har ibland en dominoeffekt - om det finns ett bevis i ett kritiskt hörn, då faller alla dominobrickor. Genombrottsresultaten, de viktigaste, kommer från en lång rad av arbete, av många olika människor, som gör stegvisa framsteg och etablerar kopplingar mellan olika frågor, tills ett stort resultat till slut visar sig.

Han nämner också en varning: medan en riktigt djävulskt snabb P = NP-algoritm skulle vara omvälvande, finns det också ett scenario där P = NP kan vara en besvikelse. Det kan visa sig att en P-algoritm som kan lösa det NP-kompletta problemet är på en tidsskala av t.ex. n ^100. Tekniskt sett faller det under P: det är ett polynom, säger James. Men n ^100 är fortfarande väldigt opraktisk – det skulle innebära att eventuella betydande problem fortfarande skulle vara utom räckhåll på mänskliga tidsskalor.

Det är, naturligtvis, förutsatt att vi kan hitta algoritmen i första hand. Donald Knuth, en algoritmist på Stanford, ändrade sig under de senaste åren - han vände på biten. Hans intuition är att P verkligen är lika med NP, men att vi förmodligen aldrig kommer att kunna använda oss av det faktum, praktiskt taget - eftersom vi faktiskt inte kommer att känna till någon av de algoritmer som råkar fungera. Det finns ett förbluffande antal algoritmer där ute, förklarar han, men de flesta av dem är bortom vår kunskap. Så medan vissa forskare kanske insisterar på att ingen P = NP-algoritm existerar, hävdar Knuth att det är mer troligt att ingen polynom-tidsalgoritm någonsin kommer att förkroppsligas - faktiskt nedskriven som ett program - av enbart dödliga.

För Papadimitriou skulle vilket svar som helst släcka en livslång besatthet. Han tror att P vs. NP-problemet hör hemma i sfären av grundläggande vetenskapliga gåtor som livets ursprung och enandet av naturens kraftfält. Det är den sortens djupgående, följdriktiga pussel, konkret men ändå universell, sa han, som ger mening inte bara till vetenskapen utan till det mänskliga livet självt.

Föreställ dig att vi har tur och att vi kan pressa ut ytterligare ett par tusen år från den här planeten, mot oddsen och trots de udda kulorna, sa han. Och vi löser inte dessa problem. Vad är poängen?!