Det 50 år gamle problem, der unddrager sig teoretisk datalogi

En løsning på P vs NP kunne låse op for utallige beregningsproblemer - eller holde dem uden for rækkevidde for altid.

Steiner-træproblemet: Forbind et sæt punkter med linjestykker med minimum total længde. Derek Brahney

ved

• Siobhan Roberts arkiv side

27. oktober 2021

en. Mandag den 19. juli 2021, midt i en anden mærkelig pandemisommer, tweetede en førende computerforsker inden for kompleksitetsteori en public service-meddelelse om en administrativ fejl i et tidsskrift. Han kvitterede med en meget belastet

Glædelig mandag.

Denne historie var en del af vores november 2021-udgave

• Se resten af ​​problemet
• Abonner

I et parallelt univers kunne det faktisk have været en meget glad mandag. Et bevis var dukket op online hos det anerkendte tidsskrift ACM Transactions on Computational Theory, som handler med fremragende original forskning, der udforsker grænserne for gennemførlig beregning. Resultatet foregav at løse problemet med alle problemer - den hellige gral af teoretisk datalogi, værd en pris på 1 million dollars og berømmelse, der konkurrerer med Aristoteles for evigt.

Dette dyrebare problem - kendt som P versus NP - betragtes på én gang som det vigtigste inden for teoretisk datalogi og matematik og helt uden for rækkevidde. Den behandler spørgsmål, der er centrale for løftet, grænserne og ambitionerne for beregning, og spørger:

Hvorfor er nogle problemer sværere end andre?

Hvilke problemer kan computere løse realistisk?

Hvor lang tid vil det tage?

Og det er en søgen med store filosofiske og praktiske gevinster.

Se, dette P versus NP spørgsmål, hvad kan jeg sige? Scott Aaronson, en datalog ved University of Texas i Austin, skrev i sin erindringer om ideer , Kvanteberegning siden Demokrit . Folk kan lide at beskrive det som ’sandsynligvis det centrale uløste problem inden for teoretisk datalogi.’ Det er en komisk underdrivelse. P vs NP er et af de dybeste spørgsmål, som mennesker nogensinde har stillet.

En måde at tænke på denne histories hovedpersoner er som følger:

P repræsenterer problemer, som en computer nemt kan løse.

NP repræsenterer problemer, som, når de er løst, er nemme at kontrollere - som puslespil eller Sudoku. Mange NP-problemer svarer til nogle af de mest genstridige og presserende problemer, samfundet står over for.

Million-dollar spørgsmålet stillet af P vs. NP er dette: Er disse to klasser af problemer en og samme? Hvilket vil sige, kunne de problemer, der virker så vanskelige, faktisk løses med en algoritme inden for rimelig tid, hvis bare den rigtige, djævelsk hurtige algoritme kunne findes? Hvis det er tilfældet, er mange svære problemer pludselig løselige. Og deres algoritmiske løsninger kunne medføre samfundsmæssige forandringer af utopiske proportioner – inden for medicin og teknik og økonomi, biologi og økologi, neurovidenskab og samfundsvidenskab, industri, kunst, endda politik og videre.

Nogle gange udvikler klassifikationerne sig - svære problemer viser sig at være nemme, når forskere finder mere effektive løsninger. Test af, om et tal er primtal, har for eksempel været kendt for at være i klassen NP siden midten af ​​1970'erne. Men i 2002 udtænkte tre dataloger ved Indian Institute of Technology Kanpur et ubetinget bevis og en smart algoritme, der endelig bekræftede, at problemet også var i P.

Hvis alle de vanskelige problemer kunne omdannes med en sådan algoritmisk håndsrækning, at konsekvenserne for samfundet – for menneskeheden og vores planet – ville være enorme.

Til at begynde med ville krypteringssystemer, hvoraf de fleste er baseret på NP-problemer, blive knækket. Vi bliver nødt til at finde en helt anden tilgang til at sende sikker kommunikation. Proteinfoldning, en 50 år gammel stor udfordring inden for biologi, ville blive mere håndterbar og frigøre nyfundne evner til at designe lægemidler, der helbreder eller behandler sygdomme og opdage enzymer, der nedbryder industriaffald. Det ville også betyde at finde optimale løsninger på hverdagens hårde problemer, såsom at kortlægge en roadtrip for at ramme alle destinationer med minimal kørsel, eller at sidde bryllupsgæster, så kun venner deler det samme middagsbord.

Siden P vs. NP-problematikkens begyndelse for 50 år siden – der dukkede op fra det betydningsfulde skæringspunkt mellem matematisk logik og elektronisk computerteknologi – har forskere over hele verden gjort herkuliske forsøg på en løsning. Nogle dataloger har foreslået, at indsatsen bedre kan sammenlignes med Sisyfos, der arbejdede uden beslutning. Men mens de, der først udforskede problemet, er ved at løbe tør for tid til at se en løsning, tager de nyere generationer med glæde op på søgen.

For Manuel Sabin, en datalog, der netop har afsluttet en ph.d.-grad ved UC Berkeley, ligger tillokken i at undersøge umuligheden af ​​problemer, hvor du ikke kender svaret, før solen opsluger jorden. Søgningen kan være quixotisk, men Sabin ville fortryde, at han ikke vippede ved disse vindmøller.

Timothy Gowers, en matematiker ved University of Cambridge, kalder det en af ​​mine personlige matematiske sygdomme. Han tabte sommeren 2013 til forfølgelsen, efter at han bad eleverne om et essay om emnet på en test. Som han fortalte på sin blog: Efter at have markeret essays i juni, tænkte jeg, at jeg bare ville bruge en time eller to på at tænke over problemet igen, og den time eller to blev ved et uheld til omkring tre måneder.

Problemet med den rejsende sælger: Find den kortest mulige rute, der besøger hver by én gang, og i sidste ende vende tilbage til oprindelsesbyen.

DEREK BRAHNEY

Søgen har endda ramt computerforskeren Stephen Cook ved University of Toronto, som indrammede problemet og lancerede feltet for beregningsmæssig kompleksitet med et banebrydende papir i 1971. For dette arbejde vandt han Turing-prisen, datalogiens ækvivalent til Nobelprisen. Men han har ikke haft held med at finde en løsning. Cook siger, at han aldrig havde nogle gode ideer - det er bare for svært.

to. Michael Sipser, en MIT-computerforsker, vurderer, at han alt i alt har brugt så meget som et årti på problemet. Han blev interesseret under kandidatskolen i 1970'erne, og han væddede på sin medstuderende Len Adleman en ounce guld på, at det ville være løst ved udgangen af ​​århundredet (Sipser betalte).

I 1980'erne opnåede han et flot resultat ved at løse en version af problemet med en begrænset beregningsmodel - hvilket førte til en spændende periode i marken med flere smukke resultater, hvilket giver anledning til håb om, at en løsning måske ikke er for langt væk.

Sipser vender stadig tilbage til problemet i ny og næ, og han er en standhaftig ambassadør, der leverer utallige foredrag om emnet.

Måden han går ind i en tilgængelig forklaring af P vs. NP på er med et grundlæggende multiplikationsproblem: 7 × 13 = ?

Svaret, 91, er nemt nok at beregne i dit hoved. Selvom det ikke er så let at gange større tal, ville det stadig tage en computer praktisk talt ingen tid overhovedet.

Men at vende disse problemer rundt er en anden sag. Overvej for eksempel at finde de to 97-cifrede primtal, der ganges for at producere dette meget store tal:

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

Dette factoring-problem var en del af en udfordring med at vurdere vanskeligheden ved at knække de RSA-nøgler, der bruges i kryptografi. At løse det tog 80 processorer fem måneders kontinuerlig computing, forklarer Sipser - hvilket svarer til omkring 33 år med kun en enkelt processor. Factoring er et hårdt problem, fordi alle nuværende metoder søger svaret via brute force og kontrollerer det astronomiske antal muligheder én efter én. Selv for en computer er dette en langsom proces.

Det interessante spørgsmål her er, skal du virkelig søge? Sipser siger. Eller er der en måde at løse factoring-problemet på, der zoomer ind på svaret hurtigt uden at søge? Vi kender ikke svaret på det spørgsmål.

Spørgsmål som dette kommer i centrum af beregningsmæssig kompleksitet - et felt fyldt med dyriske problemer, som forskere forsøger at forstå. Aaronson har samlet en Complexity Zoo, et onlinekatalog med 545 klasser af problemer (og tæller). Hver er klassificeret efter dens kompleksitet eller sværhedsgrad, og de ressourcer - tid, hukommelse, energi - der kræves for at finde løsninger. P og NP er hovedattraktionerne.

Som videnskabelig serendipity ville have det, konvergerede en sovjetisk matematiker, Leonid Levin, på et resultat svarende til Cooks på mere eller mindre samme tidspunkt.

P er klassen, der startede det hele. Det er den klasse af problemer, der kan løses af en computer inden for rimelig tid. Mere specifikt er P-problemer dem, hvor den tid det tager at finde en løsning kan beskrives ved en polynomisk funktion, som f.eks. n ^2. I polynomial-tidsalgoritmer, n er størrelsen af ​​inputtet, og væksten i forhold til det input sker med en rimelig hastighed (i dette tilfælde i kraft af to).

I modsætning hertil kan nogle hårde NP-problemer måske kun løses af algoritmer med kørselstider defineret af en eksponentiel funktion, såsom 2^n - der producerer en eksponentiel væksthastighed (som med spredningen af ​​covid). NP, som Aaronson beskriver det, er klassen af ​​knuste håb og tomme drømme. Han er dog hurtig til at afklare en almindelig misforståelse: Ikke alle NP-problemer er svære. Klassen NP indeholder faktisk klassen P - fordi problemer med nemme løsninger selvfølgelig også er nemme at kontrollere.

NPs mere udfordrende problemer har ofte betydningsfulde praktiske anvendelser. For disse problemer vil en udtømmende brute-force-søgning efter en løsning sandsynligvis fortsætte i upraktisk lang tid - geologisk tid - før et svar. Hvis en brute-force søgealgoritme er den bedst mulige algoritme, så er P ikke lig med NP.

Og blandt cognoscenti er det tilsyneladende konsensus, som nogle sammenligner mere med religiøs tro: P ≠ NP. De fleste tillader kun en smule håb om, at det modsatte vil vise sig sandt. Jeg ville give det en 2 til 3 % chance for, at P er lig med NP, siger Aaronson. Det er de odds, jeg ville tage.

Resultatet, der blev offentliggjort i juli, viste et bevis på præcis det langskud. Men det var kun det seneste i en lang tradition for beviser, der ikke består. Inden for en dag efter offentliggørelsen, i en række begivenheder, der var Monty Python værdig, blev avisen fjernet fra online-tidsskriftet; så syntes den at dukke op igen kort, før den forsvandt permanent. Det var den seneste version af et papir, som forfatteren havde postet mere end 60 gange på arXiv preprint-serveren i løbet af det sidste årti. Tidsskriftets chefredaktør forklarede på Twitter, at resultatet var blevet afvist, men i et tilfælde af menneskelige fejl var avisens disposition på en eller anden måde ændret fra afvisning til accept, og beviset havde fundet vej til offentliggørelse.

3. I begyndelsen af ​​august, da jeg mødte Steve Cook på hans kontor på campus, havde han hverken set eller hørt om det seneste P vs. NP-bevis. Nu 81 var han først for nylig gået på pension, da hans hukommelse svigtede. Det er derfor, vi har James her, sagde han - hans søn James, 36, også datalog, havde været med til mit besøg. Steve var i gang med at rydde ud i sit kontor. En gigantisk genbrugsspand stod midt i lokalet og fyldte op med gamle gulnende numre af Journal of Symbolic Logic, en stak superfede Toronto-telefonbøger, der ventede i nærheden.

I årenes løb har Cook set mange beviser, der foregiver at løse P vs. NP-problemet. I 2000, efter at Clay Mathematics Institute udnævnte det til et af de syv uløste Millennium-problemer (hver værd en pris på 1 million dollars), blev han oversvømmet med beskeder fra folk, der troede, de havde sejret. Alle resultater var forkerte, hvis ikke direkte falske. Omkring halvdelen hævdede at have bevist, at P er lig med NP; den anden halvdel gik i den modsatte retning. For ikke så længe siden hævdede en person at have bevist begge dele.

Cook formodede i sit papir fra 1971, at P ikke er lig med NP (han formulerede det ved at bruge en anden terminologi, der var almindelig på det tidspunkt). Han har siden investeret en betydelig, hvis ubestemt mængde tid i arbejdet for at fastslå, at det er tilfældet. Jeg har ikke en god hukommelse om at knokle, siger han, men hans kolleger husker, at hver gang de gik ind i afdelingen i weekenden, var Steve der på sit kontor.

Medmindre han er kapsejlads med sejlbåde, er Cook ikke en, der skynder sig; han kan lide at give en idé tid. Og hans tidligere elever husker en tydelig mangel på smæld. Datalogen Anna Lubiw ved University of Waterloo siger, at da han underviste i Cooks teorem – en del af det banebrydende papir – henviste han aldrig til det som sådan og gav aldrig engang antydninger om, at han var den person, der beviste det. Maria Klawe, en matematiker og datalog og præsidenten for Harvey Mudd College, siger, at hun regelmæssigt ville rette Cook, når han gik vild med at lære beviser på, at han vidste ud og ind: Han satte sig fast og sagde: 'Okay. Fortæl mig, hvordan beviset går.’ Cook var også berømt beskeden i ansøgninger om tilskud og rapporter vedrørende hans forskning – han ville indrømme: Helt ærligt, jeg har gjort få fremskridt …

Relateret historie

Datalogiens udvikling At beregne energiniveauerne for et heliumatom i 1958 var betydeligt sværere, end det er i dag. Men en sammenligning af dengang og nu-metoder afslører nogle kontraintuitive anomalier om indvirkningen af ​​datalogi.

Han gjorde dog fremskridt med at rekruttere James til at tage sagen op. Tidligt viste James interesse for matematik og databehandling - i en alder af ni opfordrede han sin far til at lære ham boolsk algebra og logik. For et par år siden, efter at have opnået en ph.d.-grad ved Berkeley og gjort et ophold hos Google, startede han som uafhængig forsker med fokus på diverse projekter, nogle af dem indirekte forbundet med P vs. NP. Og på trods af track record, James, der har en slående lighed med sin far, er uforskrækket over at have arvet sådan en tilsyneladende uendelig søgen. Han betragter det som enhver matematisk bestræbelse: det er et sjovt puslespil. Der skal være et svar på disse spørgsmål, siger han. Og det er ligesom, kom nu, nogen skal løse det. Lad os lige finde ud af dette. Det er længe siden. Det er pinligt, at vi ikke kender svaret endnu.

Manglen på fremskridt har ikke stoppet dette samfund af glade sisyfer fra at fejre 50-års jubilæum for beregningsmæssig kompleksitet. Festlighederne begyndte i 2019, da hengivne fra hele verden samledes på Fields Institute for Research in Mathematical Sciences, ved University of Toronto, til et symposium til Cooks ære. Christos Papadimitriou, en datalog ved Columbia University, som har brugt meget af sin karriere på at arbejde på P vs. NP, åbnede begivenheden med et offentligt foredrag, hvor han kiggede ikke et halvt århundrede tilbage, men årtusinder.

Han begyndte med at beskrive ældgamle quests for løsninger - ved hjælp af algebraiske værktøjer eller straightedge og kompas, som han anså for rudimentære former for beregning. Papadimitrious fortælling ankom til sidst til Alan Turing, den britiske matematiker, hvis papir fra 1936 On Computable Numbers formaliserede forestillingerne om algoritme og beregning. Turing viste også – med sin idé om en universel computermaskine – at der ikke er nogen mekanisk måde (det vil sige udført af en maskine) til at bevise sandheden eller usandheden af ​​matematiske udsagn; ingen systematisk måde at skelne det beviselige fra det ubeviselige på.

Papadimitriou sagde, at han betragter Turings papir som datalogiens fødselsattest - og fødselsattesten siger, at datalogi blev født med en skarp forståelse af sine egne begrænsninger. Han regnede med, at datalogi er det eneste kendte område af videnskabelig diskurs, der er født med en sådan bevidsthed - i modsætning til andre videnskaber, der forstår deres egne begrænsninger, ligesom resten af ​​os, i den sene middelalder.

Det var ikke længe efter, at Turings ideer (og lignende ideer fra andre) fandt legemliggørelse i de første computere, at videnskabsmænd konfronterede spørgsmål om maskinernes iboende muligheder og begrænsninger. I begyndelsen af ​​1950'erne pralede John von Neumann, den ungarsk-amerikanske pioner inden for den moderne computer, med en algoritme om, at han var polynomium sammenlignet med den eksponentielle etablerede, som Papadimitriou huskede - han havde overlistet en langsom algoritme med en hurtig. Dette var begyndelsen til en ny teori: beregningsmæssig kompleksitetsteori. Kernen i det var, at kun polynomielle algoritmer på nogen måde er gode eller praktiske eller værd at sigte mod et problem, hvorimod en eksponentiel algoritme, sagde Papadimitriou, er den algoritmiske ækvivalent til død.

Cook begyndte først at tænke på kompleksitet i midten af ​​1960'erne. Mens han arbejdede på sin ph.d.-grad på Harvard, overvejede han, om det er muligt at bevise, givet visse beregningsmodeller, at multiplikation er sværere end addition (det forbliver et åbent problem).

I 1967 udarbejdede han ifølge en bog om Cook fra Association for Computing Machinery (ACM), mens han var postdoc hos Berkeley, kursusnotater, der indeholdt kimen til hans store resultat. Han havde udarbejdet en formulering af de kompleksitetsklasser, der blev kendt som P og NP, og han stillede spørgsmålet, om P var lig med NP. (På samme tid kredsede andre, inklusive datalogen Jack Edmonds, nu pensioneret fra University of Waterloo, om de samme ideer.)

Men området for datalogi var kun lige begyndt, og for de fleste videnskabsmænd og matematikere var sådanne ideer ukendte, hvis ikke direkte mærkelige. Efter fire år på Berkeleys matematikafdeling blev Cook overvejet at ansætte, men ikke tilbudt en stilling. Han havde advokater i universitetets nye afdeling for datalogi, og de lobbyede for, at han skulle få en stilling i deres rækker, men dekanen var ikke tilbøjelig til at give en embedsperiode til en, som de berømte matematikere havde nægtet.

De fleste kompleksitetsteoretikere drømmer lidt mindre og vælger i stedet indirekte tilgange.

I 1970 flyttede Cook til University of Toronto. Året efter offentliggjorde han sit gennembrud. Indsendt til et symposium af ACM afholdt i maj i Shaker Heights, Ohio, skærpede papiret begrebet kompleksitet og definerede en måde at karakterisere de sværeste problemer i NP. Det beviste, i et glimt af algoritmisk alkymi, at et problem, kendt som tilfredshedsproblemet (at søge en løsning på en formel givet et sæt begrænsninger), på en måde var det sværeste problem i NP, og at alle de andre NP-problemer kunne reduceres til det.

Dette var et afgørende teorem: Hvis der er en polynomiel-tidsalgoritme, der løser tilfredshedsproblemet, så vil den algoritme tjene som en skeletnøgle, der låser op for løsninger på alle problemerne i NP. Og hvis der findes en polynomiel-tidsløsning for alle problemerne i NP, så er P = NP.

Blandt dataloger er Cooks teorem ikonisk. Leslie Valiant fra Harvard huskede på symposiet i 2019 præcis, hvor og hvornår han først hørte om det. Efter at have afsluttet bachelorstudier i matematik, var han startet på en ph.d. i datalogi. Mens der var kurser og grader i dette spæde felt, sagde han, føltes det flygtigt, måske manglede det dybe intellektuelle indhold. Det var en alvorlig bekymring for folk, der dyrkede datalogi på det tidspunkt, sagde han. De spurgte: ’Er dette en mark? Hvor skal det hen?’ En dag stødte Valiant på Cooks papir. Han læste det natten over. Jeg blev forvandlet, sagde han. På et øjeblik blev mine bekymringer om datalogi meget reduceret. Dette papir - for mig gjorde det virkelig feltet. Jeg tror, ​​det gjorde datalogi - gjorde det til noget af substans.

Og så, som historien siger, efter Cooks teorem kom en syndflod.

I 1972 påviste Dick Karp, en datalog ved Berkeley, efter at have læst Cooks esoteriske papir, at mange af de klassiske beregningsproblemer, som han var fortrolig med - i det væsentlige ethvert problem, han ikke vidste, hvordan han skulle løse, hentet fra matematisk programmering, operationsforskning, grafteori, kombinatorik og beregningslogik - besad den samme transformationsegenskab, som Cook havde fundet med tilfredshedsproblemet. I alt fandt Karp 21 problemer, inklusive rygsækproblemet (søger den optimale måde at pakke et begrænset rum med de mest værdifulde genstande), problemet med sælgerrejsende (at finde den kortest mulige rute, der besøger hver by én gang og vender tilbage til byen af oprindelse), og Steiner-træproblemet (søger at forbinde et sæt punkter optimalt med linjestykker med minimum total længde).

Karp viste, at denne særlige samling af problemer alle var ækvivalente, hvilket igen viste, at det mønster, som Cook identificerede, ikke var et isoleret fænomen, men snarere en klassifikationsmetodologi med overraskende magt og rækkevidde. Det var en slags lakmusprøve, der identificerede klassen af, hvad der blev kendt som NP-komplette problemer: en løsning på nogen ville knække dem alle.

Papadimitriou tænker på NP-fuldstændighed som et alsidigt værktøj. Hvis du ikke kan løse et problem, så prøv at bevise, at det er NP-komplet, for det vil måske spare dig for en masse tid, sagde han ved det offentlige foredrag - du kan opgive en nøjagtig løsning og gå videre til at løse en tilnærmelse eller variation af problemet i stedet.

I historiens store fejring ser Papadimitriou fænomenet NP-fuldstændighed og P vs. NP-missionen som datalogiens skæbne. For som videnskabelig serendipitet ville have det, konvergerede en sovjetisk matematiker, Leonid Levin, på et resultat svarende til Cooks på mere eller mindre samme tidspunkt. Levin, nu ved Boston University, udførte sit arbejde bag jerntæppet. Efter at det fik større opmærksomhed (han immigrerede til Amerika i 1978), blev resultatet kendt som Cook-Levin-sætningen.

Og i en yderligere coda et årti eller deromkring senere blev et tabt brev opdaget i Princeton-arkiverne af den østrigske logiker Kurt Gödel. I 1956 havde han skrevet til von Neumann og spurgt, om et logisk problem - som i moderne sprogbrug ville blive kaldt NP-komplet - kunne løses i polynomisk tid. Han mente, at dette ville få konsekvenser af den største størrelse.

Klikeproblemet: Søg efter kliker i en graf, såsom en bestemt undergruppe af venner i et socialt netværk.

DEREK BRAHNEY

Fire. Selvom et halvt århundredes arbejde ikke har givet noget nær en løsning, fanger nogle resultater i det mindste fantasien: et papir i 2004 hævdede et bevis for P = NP ved hjælp af sæbebobler som en mekanisme til analog beregning (sæbefilm, naturligvis justering i minimumsenergikonfigurationen løser det NP-komplette Steiner-træproblem på en måde).

I disse dage er det en sjælden fugl af en computerforsker - for eksempel Ron Fagin, en IBM-stipendiat - der tager fat på problemet. I 1970'erne fremstillede han Fagins teorem, som karakteriserede klassen NP med hensyn til matematisk logik. Og han har løst problemet mere end én gang, men resultaterne stod aldrig i mere end et par dage, før han fandt en fejl. Fagin modtog for nylig finansiering til et P vs. NP-projekt fra IBMs Exploratory Challenges-program, der støtter eventyrlysten forskning. Når han forklarer, hvorfor han bliver ved med det, citerer han gerne Theodore Roosevelt, der sagde, at det er langt bedre at vove mægtige ting end at rangere blandt dem, der lever i et gråt tusmørke, der hverken kender sejr eller nederlag.

Men de fleste kompleksitetsteoretikere drømmer lidt mindre og vælger i stedet for indirekte tilgange – vippe problemet, omforme eller omformulere det, udforske relaterede omgivelser og yderligere nedskære arsenalet af værktøjer, der kunne bruges mod det (mange er nu kendt for at være ubrugelige ).

Ryan Williams, en datalog ved MIT, forsøger at belyse problemet både oppefra og nedefra - undersøger karakteren af ​​øvre og nedre grænser på kerneberegningsproblemer. En øvre grænse er i enkle vendinger en specifik matematisk påstand om, at der eksisterer en konkret algoritme, der løser et bestemt problem uden at overskride en vis mængde ressourcer (tid, hukommelse, energi). En nedre grænse er den immaterielle modsætning: det er en generel påstand om umulighed, der viser, at en sådan algoritme ikke eksisterer universelt. Et fokus i Williams' forskning er at gøre nedre grænser konstruktive og konkrete - matematiske objekter med beskrivelige træk. Han mener, at mere konstruktive tilgange til nedre grænser netop er det, vi mangler fra nuværende tilgange inden for kompleksitetsteori.

Williams har fastlagt sandsynligheden for, at P ≠ NP er temmelig moderate 80 %. Men på det seneste udtrykker nogle forskere på området tvivl om selv det niveau af sikkerhed. Mere og mere begynder jeg at spekulere på, om P er lig med NP, siger Toniann Pitassi, en datalog ved University of Toronto og en tidligere ph.d.-studerende fra Cook's. Hendes tilgang til at cirkle rundt om problemet er at studere både opskalerede og nedskalerede analoger, hårdere og nemmere modeller. Nogle gange bliver det klarere at generalisere spørgsmålet, siger hun. Men overordnet set har hun ikke opnået klarhed: De fleste mennesker tror, ​​at P ikke er lig med NP. Og jeg ved det ikke. Måske er det bare mig, men jeg føler, at det er blevet mindre og mindre klart, at det er sandheden.

Historisk, påpeger Pitassi, er overraskende resultater lejlighedsvis kommet ud af ingenting - tilsyneladende umuligheder, der har vist sig at være mulige af smarte algoritmedesignere. Det samme kunne ske med P vs. NP, måske om yderligere 50 år eller et århundrede. Et af de vigtigste resultater inden for hele kompleksitetsteorien blev for eksempel opnået af David Barrington fra University of Massachusetts, Amherst, i 1989. Kernen i det (til vores formål) er, at han udtænkte en smart algoritme, som satte sig for at gøre noget, der tilsyneladende skulle have krævet en ubegrænset mængde hukommelse, men som faktisk brugte en forbløffende lille mængde - kun fem bit information, nok til at angive et tal mellem et og 32 (inklusive) eller et ord på to bogstaver.

Et nyere og relateret resultat, fra 2014, overraskede James Cook. Med udgangspunkt i Barringtons teorem bruger den hukommelsen på en vidunderlig mærkelig måde. Som antydet i titlen på papiret, af University of Amsterdams Harry Buhrman og samarbejdspartnere, handler det om computing med fuld hukommelse. James kan næsten ordret skråle fra avisens indledende afsnit:

Forestil dig følgende scenarie. Du ønsker at udføre en beregning, der kræver mere hukommelse, end du i øjeblikket har tilgængelig på din computer. En måde at håndtere dette problem på er ved at installere en ny harddisk. Som det viser sig, har du en harddisk, men den er fyldt med data, billeder, film, filer osv. Du behøver ikke at få adgang til disse data i øjeblikket, men du vil heller ikke slette dem. Kan du bruge harddisken til din beregning, muligvis ændre dens indhold midlertidigt, og garantere, at når beregningen er afsluttet, er harddisken tilbage i sin oprindelige tilstand med alle data intakte?

Svaret, kontraintuitivt, er ja.

James opfatter det som et lånt minde. Efter at chokket over dette resultat sank ind, havde han det sjovt med at finde ud af, hvordan han skulle anvende det på et bestemt problem – at fortsætte, hvor hans far slap.

For et par årtier siden gik Steve Cook videre til andre relaterede problemer inden for kompleksitetsteori. Med et problem lavede han en formodning om mængden af ​​hukommelse, en algoritme ville have brug for for at løse problemet - at finpudse det til det absolutte minimum. I 2019 implementerede James sammen med Ian Mertz, en af ​​Pitassis ph.d.-studerende, den poetiske idé om at låne hukommelse og beviste, at der var brug for endnu mindre hukommelse. Resultatet gik ikke hele vejen til at modbevise hans fars formodning, men det er ikke desto mindre et lille fremskridt i den store kompleksitetsmission.

Og problemer i kompleksitetsteorien, bemærker James, har nogle gange en dominoeffekt - hvis der er et bevis i et kritisk hjørne, så falder alle dominobrikkerne. Gennembrudsresultaterne, de vigtigste, kommer fra en lang række af arbejde, udført af en masse forskellige mennesker, der gør gradvise fremskridt og etablerer forbindelser mellem forskellige spørgsmål, indtil der til sidst viser sig et stort resultat.

Han nævner også en advarsel: mens en virkelig djævelsk hurtig P = NP-algoritme ville være verdensomspændende, er der også et scenarie, hvor P = NP kan være en nedtur. Det kan vise sig, at en P-algoritme, der er i stand til at løse det NP-komplette problem, er på en tidsskala på f.eks. n ^100. Teknisk set falder det under P: det er et polynomium, siger James. Men n ^100 er stadig meget upraktisk - det ville betyde, at alle betydelige problemer stadig ville være uden for rækkevidde på menneskelige tidsskalaer.

Det er selvfølgelig forudsat, at vi kan finde algoritmen i første omgang. Donald Knuth, en algoritmist hos Stanford, har i de senere år ændret mening - han vendte lidt om. Hans intuition er, at P faktisk er lig med NP, men at vi formentlig aldrig vil være i stand til at gøre brug af det faktum, praktisk talt - fordi vi faktisk ikke kender nogen af ​​de algoritmer, der tilfældigvis virker. Der er forbløffende mange algoritmer derude, forklarer han, men de fleste af dem er uden for vores viden. Så mens nogle forskere måske insisterer på, at der ikke eksisterer en P = NP-algoritme, hævder Knuth, at det er mere sandsynligt, at ingen polynomiel-tidsalgoritme nogensinde vil blive legemliggjort - faktisk nedskrevet som et program - af rene dødelige.

For Papadimitriou ville ethvert svar slukke en livslang besættelse. Han mener, at P vs. NP-problemet hører hjemme i området for grundlæggende videnskabelige gåder såsom livets oprindelse og foreningen af ​​naturens kraftfelter. Det er den slags dybtgående, konsekvente puslespil, konkret og alligevel universel, sagde han, der tilføjer mening ikke kun til videnskaben, men til selve menneskelivet.

Forestil dig, at vi er heldige, og vi er i stand til at presse endnu et par tusinde år ud af denne planet, mod oddsene og på trods af de skæve ting, sagde han. Og vi løser ikke disse problemer. Hvad er pointen?!