Het 50 jaar oude probleem dat theoretische informatica ontgaat

Een oplossing voor P versus NP zou talloze rekenproblemen kunnen ontsluiten - of ze voor altijd buiten bereik houden.

Het Steinerboomprobleem: verbind een reeks punten met lijnstukken met een minimale totale lengte. Derek Brahney

door

• Siobhan Roberts archiefpagina

27 oktober 2021

een. Op maandag 19 juli 2021, midden in weer een vreemde pandemische zomer, tweette een vooraanstaande computerwetenschapper op het gebied van complexiteitstheorie een openbare dienstbericht over een administratieve snafu in een tijdschrift. Hij tekende af met een zeer beladen

Gelukkige maandag.

Dit verhaal maakte deel uit van ons nummer van november 2021

• Zie de rest van het nummer
• Abonneren

In een parallel universum zou het inderdaad een heel gelukkige maandag zijn geweest. Een bewijs was online verschenen in het gerenommeerde tijdschrift ACM Transactions on Computational Theory, dat handelt in uitstekend origineel onderzoek dat de grenzen van haalbare berekeningen verkent. Het resultaat was bedoeld om het probleem van alle problemen op te lossen - de heilige graal van de theoretische informatica, ter waarde van een prijs van $ 1 miljoen en roem die voor altijd wedijvert met die van Aristoteles.

Dit gekoesterde probleem - bekend als P versus NP - wordt beschouwd als het belangrijkste in de theoretische informatica en wiskunde en is volledig buiten bereik. Het behandelt vragen die centraal staan ​​in de belofte, limieten en ambities van berekeningen, en vraagt:

Waarom zijn sommige problemen moeilijker dan andere?

Welke problemen kunnen computers realistisch oplossen?

Hoe lang gaat het duren?

En het is een zoektocht met grote filosofische en praktische uitbetalingen.

Kijk, deze P versus NP-vraag, wat kan ik zeggen? Scott Aaronson, een computerwetenschapper aan de Universiteit van Texas in Austin, schreef in zijn memoires van ideeën , Quantum Computing sinds Democritus . Mensen omschrijven het graag als 'waarschijnlijk het centrale onopgeloste probleem van de theoretische informatica'. Dat is een komisch understatement. P vs NP is een van de diepste vragen die mensen ooit hebben gesteld.

Een manier om aan de hoofdpersonen van dit verhaal te denken is als volgt:

P staat voor problemen die een computer handig kan oplossen.

NP staat voor problemen die, eenmaal opgelost, gemakkelijk te controleren zijn, zoals legpuzzels of Sudoku. Veel NP-problemen komen overeen met enkele van de meest hardnekkige en urgente problemen waarmee de samenleving wordt geconfronteerd.

De vraag van een miljoen dollar die P vs. NP stelt, is deze: zijn deze twee klassen van problemen één en dezelfde? Dat wil zeggen, zouden de problemen die zo moeilijk lijken in feite binnen een redelijke tijd kunnen worden opgelost met een algoritme, als er maar het juiste, duivels snelle algoritme zou worden gevonden? Dan zijn veel moeilijke problemen ineens oplosbaar. En hun algoritmische oplossingen zouden maatschappelijke veranderingen van utopische proporties teweeg kunnen brengen - in geneeskunde en techniek en economie, biologie en ecologie, neurowetenschappen en sociale wetenschappen, industrie, kunst, zelfs politiek en daarbuiten.

Soms evolueren de classificaties - harde problemen blijken gemakkelijk te zijn wanneer onderzoekers efficiëntere oplossingen vinden. Testen of een getal priemgetal is, is bijvoorbeeld bekend sinds het midden van de jaren zeventig in de klasse NP. Maar in 2002 bedachten drie computerwetenschappers van het Indian Institute of Technology Kanpur een onvoorwaardelijk bewijs en een slim algoritme dat uiteindelijk bevestigde dat het probleem ook in P.

Als allemaal de lastige problemen zouden kunnen worden getransformeerd met zo'n algoritmische handigheid, de gevolgen voor de samenleving - voor de mensheid en onze planeet - zouden enorm zijn.

Om te beginnen zouden encryptiesystemen, waarvan de meeste gebaseerd zijn op NP-problemen, worden gekraakt. We zouden een heel andere benadering moeten vinden voor het verzenden van veilige communicatie. Eiwitvouwing, een 50 jaar oude grote uitdaging in de biologie, zou beter handelbaar worden en nieuwe vaardigheden ontsluiten om medicijnen te ontwerpen die ziekten genezen of behandelen en om enzymen te ontdekken die industrieel afval afbreken. Het zou ook betekenen dat je optimale oplossingen moet vinden voor alledaagse problemen, zoals het uitstippelen van een roadtrip om alle bestemmingen te bereiken met een minimum aan autorijden, of het plaatsen van bruiloftsgasten zodat alleen vrienden aan dezelfde eettafel zitten.

Sinds het begin van het P vs. NP-probleem, 50 jaar geleden - ontstaan ​​uit de gedenkwaardige kruising van wiskundige logica en elektronische computertechnologie - hebben onderzoekers over de hele wereld enorme pogingen gedaan om een ​​oplossing te vinden. Sommige computerwetenschappers hebben gesuggereerd dat de inspanningen misschien beter te vergelijken zijn met die van Sisyphus, die zonder vastberadenheid werkte. Maar terwijl degenen die het probleem voor het eerst hebben onderzocht, bijna geen tijd meer hebben om een ​​oplossing te zien, gaan de nieuwere generaties vrolijk verder met de zoektocht.

Voor Manuel Sabin, een computerwetenschapper die net een doctoraat aan UC Berkeley heeft afgerond, ligt de aantrekkingskracht in het onderzoeken van de onmogelijkheid van problemen waarvan je het antwoord pas weet als de zon de aarde overspoelt. De zoektocht mag dan quixotisch zijn, maar Sabin zou er spijt van krijgen dat hij niet naar deze windmolens had gekanteld.

Timothy Gowers, een wiskundige aan de Universiteit van Cambridge, noemt het een van mijn persoonlijke wiskundige ziekten. Hij verloor de zomer van 2013 aan de achtervolging, nadat hij op een toets studenten om een ​​opstel over het onderwerp had gevraagd. Zoals hij op zijn blog vertelde: Nadat ik de essays in juni had nagekeken, dacht ik dat ik nog een uur of twee over het probleem zou nadenken, en dat paar uur werden per ongeluk ongeveer drie maanden.

Het handelsreizigersprobleem: vind de kortst mogelijke route die elke stad één keer aandoet en uiteindelijk terugkeert naar de stad van herkomst.

DEREK BRAHNEY

De zoektocht heeft zelfs de computerwetenschapper Stephen Cook van de Universiteit van Toronto met stomheid geslagen, die het probleem in kaart bracht en het gebied van computationele complexiteit in 1971 met een baanbrekend artikel lanceerde. Voor dit werk won hij de Turing Award, het informatica-equivalent van de Nobelprijs. Maar hij heeft geen geluk gehad met het vinden van een oplossing. Cook zegt dat hij nooit goede ideeën heeft gehad - het is gewoon te moeilijk.

twee. Michael Sipser, een computerwetenschapper van het MIT, schat dat hij in totaal wel tien jaar aan het probleem heeft besteed. Hij raakte geïnteresseerd tijdens zijn afstuderen in de jaren zeventig en hij wedde met zijn medestudent Len Adleman een ons goud dat het tegen het einde van de eeuw zou zijn opgelost (Sipser heeft betaald).

In de jaren tachtig behaalde hij een mooi resultaat door een versie van het probleem op te lossen met een beperkt rekenmodel - wat leidde tot een opwindende periode in het veld met verschillende mooie resultaten, die hoop geven dat een oplossing misschien niet al te ver weg is.

Sipser komt nog steeds af en toe terug op het probleem, en hij is een standvastige ambassadeur die talloze lezingen over het onderwerp houdt.

De manier waarop hij in een toegankelijke verklaring van P vs. NP komt, is met een basisvermenigvuldigingsprobleem: 7 × 13 = ?

Het antwoord, 91, is eenvoudig genoeg om in je hoofd te berekenen. Hoewel het vermenigvuldigen van grotere getallen niet zo eenvoudig is, zou het een computer toch praktisch geen tijd kosten.

Maar die problemen omdraaien is een andere zaak. Overweeg bijvoorbeeld om de twee 97-cijferige priemgetallen te vinden die zich vermenigvuldigen om dit zeer grote getal te produceren:

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

Dit factoringprobleem maakte deel uit van een uitdaging om de moeilijkheid te beoordelen van het kraken van de RSA-sleutels die in cryptografie worden gebruikt. Om het op te lossen waren 80 processors vijf maanden continu computeren nodig, legt Sipser uit, wat neerkomt op ongeveer 33 jaar met slechts een enkele processor. Factoring is een moeilijk probleem omdat alle huidige methoden het antwoord zoeken met brute kracht, waarbij ze het astronomische aantal mogelijkheden één voor één controleren. Zelfs voor een computer is dit een langzaam proces.

De interessante vraag is: moet je echt zoeken? zegt Sipser. Of is er een manier om het factoringprobleem op te lossen dat snel inzoomt op het antwoord zonder te zoeken? We weten het antwoord op die vraag niet.

Vragen als deze raken de kern van computationele complexiteit - een veld vol beestachtige problemen die onderzoekers proberen te begrijpen. Aaronson heeft een Complexity Zoo samengesteld, een online catalogus met 545 probleemklassen (en nog steeds). Elk is geclassificeerd op basis van zijn complexiteit of moeilijkheidsgraad en de middelen - tijd, geheugen, energie - die nodig zijn om oplossingen te vinden. P en NP zijn de belangrijkste attracties.

Zoals wetenschappelijke serendipiteit zou willen, kwam een ​​Sovjet-wiskundige, Leonid Levin, min of meer tegelijkertijd tot een resultaat dat equivalent was aan dat van Cook.

P is de klasse waarmee het allemaal begon. Het is de klasse van problemen die door een computer in een redelijke tijd kunnen worden opgelost. Meer specifiek zijn P-problemen die waarvoor de tijd die nodig is om een ​​oplossing te vinden kan worden beschreven door een polynoomfunctie, zoals N ^2. In polynomiale tijdalgoritmen, N is de grootte van de input, en de groei tegen die input vindt plaats in een redelijk tempo (in dit geval tot de macht twee).

Daarentegen zijn sommige harde NP-problemen mogelijk alleen oplosbaar door algoritmen met looptijden gedefinieerd door een exponentiële functie, zoals 2 ^ n, wat een exponentiële groeisnelheid oplevert (zoals bij de verspreiding van covid). NP, zoals Aaronson het beschrijft, is de klasse van vervlogen hoop en ijdele dromen. Een veelvoorkomende misvatting maakt hij echter snel duidelijk: niet alle NP-problemen zijn moeilijk. De klasse NP bevat namelijk de klasse P - omdat problemen met eenvoudige oplossingen natuurlijk ook gemakkelijk te controleren zijn.

De meer uitdagende problemen van NP hebben vaak belangrijke praktische toepassingen. Voor deze problemen zou een uitputtende zoektocht met brute kracht naar een oplossing waarschijnlijk een onpraktisch lange tijd duren - geologische tijd - voordat een antwoord zou worden gegeven. Als een brute-force zoekalgoritme het best mogelijke algoritme is, dan is P niet gelijk aan NP.

En onder de kenners is dat blijkbaar de consensus, die sommigen meer vergelijken met religieus geloof: P ≠ NP. De meesten laten slechts een sprankje hoop toe dat het tegendeel waar zal blijken te zijn. Ik zou het een kans van 2 tot 3% geven dat P gelijk is aan NP, zegt Aaronson. Dat zijn de weddenschappen die ik zou nemen.

Het resultaat dat in juli werd gepubliceerd, leverde een bewijs van precies dat afstandsschot. Maar het was pas de laatste in een lange traditie van bewijzen die niet door de beugel kunnen. Binnen een dag na publicatie, in een gang van zaken die Monty Python waardig was, werd het artikel uit het online tijdschrift verwijderd; toen leek het even weer te verschijnen voordat het definitief verdween. Het was de meest recente versie van een paper die de auteur de afgelopen tien jaar meer dan 60 keer op de preprint-server van arXiv had geplaatst. De hoofdredacteur van het tijdschrift legde op Twitter uit dat het resultaat was afgewezen, maar in het geval van een menselijke fout was de dispositie van de krant op de een of andere manier veranderd van afwijzen naar accepteren en had het bewijs zijn weg naar publicatie gevonden.

3. Toen ik begin augustus Steve Cook ontmoette op zijn kantoor op de campus, had hij die laatste P vs. NP-proof snafu niet gezien of gehoord. Nu 81, was hij pas onlangs met pensioen gegaan, omdat zijn geheugen het liet afweten. Daarom hebben we James hier, zei hij - zijn zoon James, 36, ook een computerwetenschapper, was bij ons op bezoek geweest. Steve was bezig zijn kantoor op te ruimen. Een gigantische prullenbak stond in het midden van de kamer en vulde zich met oude vergeling van de Journal of Symbolic Logic, een stapel superdikke Toronto-telefoonboeken die in de buurt stonden te wachten.

In de loop der jaren heeft Cook veel bewijzen gezien die beweerden het P vs. NP-probleem op te lossen. In 2000, nadat het Clay Mathematics Institute het een van de zeven onopgeloste millenniumproblemen noemde (elk een prijs van $ 1 miljoen waard), werd hij overspoeld met berichten van mensen die dachten dat ze hadden gezegevierd. Alle resultaten waren verkeerd, zo niet ronduit nep. Ongeveer de helft beweerde te hebben bewezen dat P gelijk is aan NP; de andere helft ging in de tegenovergestelde richting. Nog niet zo lang geleden beweerde één persoon beide te hebben bewezen.

Cook vermoedde in zijn artikel uit 1971 dat P niet gelijk is aan NP (hij formuleerde het in een andere terminologie die destijds gebruikelijk was). Sindsdien heeft hij een aanzienlijke, zij het onbepaalde hoeveelheid tijd geïnvesteerd om vast te stellen dat dat het geval is. Ik heb geen goede herinnering aan zwoegen, zegt hij, maar zijn collega's herinneren zich dat wanneer ze in het weekend naar de afdeling gingen, Steve daar in zijn kantoor was.

Tenzij hij met zeilboten racet, is Cook niet iemand die zich haast; hij geeft graag een idee tijd. En zijn oud-studenten herinneren zich een duidelijk gebrek aan branie. De computerwetenschapper Anna Lubiw van de Universiteit van Waterloo zegt dat hij, toen hij de stelling van Cook leerde - een deel van dat baanbrekende artikel - er nooit naar verwees als zodanig en zelfs geen enkele aanwijzing gaf dat hij de persoon was die het bewees. Maria Klawe, een wiskundige en informaticus en de president van Harvey Mudd College, zegt dat ze Cook regelmatig corrigeerde als hij de weg kwijt was en bewijzen dat hij het door en door wist: hij zou vast komen te zitten en zeggen: 'Oké. Vertel me hoe het bewijs gaat.' Cook was ook beroemd bescheiden in subsidieaanvragen en rapporten met betrekking tot zijn onderzoek - hij zou bekennen: eerlijk gezegd heb ik weinig vooruitgang geboekt ...

Verwant verhaal

De evolutie van informatica Het berekenen van de energieniveaus van een heliumatoom in 1958 was aanzienlijk moeilijker dan het nu is. Maar een vergelijking van methoden van toen en nu onthult enkele contra-intuïtieve anomalieën over de impact van informatica.

Hij boekte echter vooruitgang door James te rekruteren om de zaak op zich te nemen. Al vroeg toonde James interesse in wiskunde en informatica - toen hij negen was, drong hij er bij zijn vader op aan hem Booleaanse algebra en logica te leren. Een paar jaar geleden, na het behalen van een doctoraat in Berkeley en een periode bij Google, ging hij als onafhankelijk onderzoeker aan de slag met diverse projecten, waarvan sommige indirect verband hielden met P vs. NP. En ondanks het trackrecord, is James, die een opvallende gelijkenis vertoont met zijn vader, onverschrokken dat hij zo'n schijnbaar eindeloze zoektocht heeft geërfd. Hij beschouwt het als elke wiskundige onderneming: het is een leuke puzzel. Op deze vragen moet een antwoord komen, zegt hij. En het is alsof, kom op, iemand moet het oplossen. Laten we dit gewoon uitzoeken. Het is lang geleden. Het is beschamend dat we het antwoord nog niet weten.

Het gebrek aan vooruitgang heeft deze gemeenschap van gelukkige Sisypheans er niet van weerhouden om het 50-jarig jubileum van computationele complexiteit te vieren. De festiviteiten begonnen in 2019, toen toegewijden van over de hele wereld zich verzamelden bij het Fields Institute for Research in Mathematical Sciences, aan de Universiteit van Toronto, voor een symposium ter ere van Cook. Christos Papadimitriou, een computerwetenschapper aan de Columbia University die een groot deel van zijn carrière aan P vs. NP heeft gewerkt, opende het evenement met een openbare lezing, waarin hij niet een halve eeuw maar millennia terugblikte.

Hij begon met het beschrijven van eeuwenoude zoektochten naar oplossingen - met behulp van algebraïsche hulpmiddelen of liniaal en kompas, die hij als rudimentaire vormen van berekening beschouwde. Papadimitriou's verhaal kwam uiteindelijk aan bij Alan Turing, de Britse wiskundige wiens paper On Computable Numbers uit 1936 de noties van algoritme en berekening formaliseerde. Turing toonde ook aan - met zijn idee van een universele computermachine - dat er geen mechanische manier is (dat wil zeggen, uitgevoerd door een machine) om de waarheid of onwaarheid van wiskundige uitspraken te bewijzen; geen systematische manier om het bewijsbare van het onbewijsbare te onderscheiden.

Papadimitriou zei dat hij Turing's paper beschouwt als de geboorteakte van de informatica - en de geboorteakte zegt dat de informatica is geboren met een scherp begrip van haar eigen beperkingen. Hij dacht dat computerwetenschap het enige bekende gebied van wetenschappelijke verhandeling is dat met een dergelijk bewustzijn is geboren - in tegenstelling tot andere wetenschappen, die hun eigen beperkingen begrijpen, zoals de rest van ons, op late middelbare leeftijd.

Het duurde niet lang nadat de ideeën van Turing (en soortgelijke ideeën van anderen) belichaamd werden in de eerste computers dat wetenschappers vragen stelden over de inherente mogelijkheden en beperkingen van de machines. In het begin van de jaren vijftig schepte John von Neumann, de Hongaars-Amerikaanse pionier van de moderne computer, op over een algoritme dat hij polynoom was, vergeleken met de exponentiële gevestigde exploitant, zoals Papadimitriou zich herinnerde - hij was een langzaam algoritme te slim af met een snel algoritme. Dit was het begin van een nieuwe theorie: computationele complexiteitstheorie. De kern ervan was dat alleen polynomiale algoritmen in zekere zin goed of praktisch zijn of de moeite waard zijn om op een probleem te richten, terwijl een exponentieel algoritme, zei Papadimitriou, het algoritmische equivalent van de dood is.

Cook begon halverwege de jaren zestig na te denken over complexiteit. Terwijl hij aan zijn doctoraat aan Harvard werkte, vroeg hij zich af of het mogelijk is om, gegeven bepaalde rekenmodellen, te bewijzen dat vermenigvuldigen moeilijker is dan optellen (het blijft een open probleem).

In 1967 schreef hij, volgens een boek over Cook van de Association for Computing Machinery (ACM), terwijl hij een postdoc in Berkeley was, cursusnota's die de kiem van zijn grote resultaat bevatten. Hij had een formulering uitgewerkt van de complexiteitsklassen die bekend kwamen te staan ​​als P en NP, en hij stelde de vraag of P gelijk was aan NP. (Rond dezelfde tijd cirkelden anderen, waaronder de computerwetenschapper Jack Edmonds, nu met pensioen van de Universiteit van Waterloo, rond dezelfde ideeën.)

Maar het gebied van de informatica was nog maar net begonnen, en voor de meeste wetenschappers en wiskundigen waren dergelijke ideeën onbekend, zo niet ronduit vreemd. Na vier jaar op de wiskundeafdeling van Berkeley, kwam Cook in aanmerking voor een vaste aanstelling, maar kreeg hij geen baan aangeboden. Hij had pleitbezorgers in de nieuwe afdeling computerwetenschappen van de universiteit, en ze lobbyden ervoor dat hij een positie in hun gelederen zou krijgen, maar de decaan was niet geneigd iemand een vaste aanstelling te geven die de illustere wiskundigen hadden ontkend.

De meeste complexiteitstheoretici dromen een beetje kleiner en kiezen in plaats daarvan voor indirecte benaderingen.

In 1970 verhuisde Cook naar de Universiteit van Toronto. Het jaar daarop publiceerde hij zijn doorbraak. De paper, die werd voorgelegd aan een symposium van de ACM dat in mei in Shaker Heights, Ohio werd gehouden, verscherpte het concept van complexiteit en definieerde een manier om de moeilijkste problemen in NP te karakteriseren. Het bewees, in een flits van algoritmische alchemie, dat één probleem, bekend als het vervulbaarheidsprobleem (een oplossing zoeken voor een formule met een reeks beperkingen), in zekere zin het moeilijkste probleem in NP was, en dat alle andere NP-problemen zou er toe kunnen worden teruggebracht.

Dit was een cruciale stelling: als er een polynomiaal-tijdalgoritme is dat het vervulbaarheidsprobleem oplost, dan zal dat algoritme dienen als een skeletsleutel, waarmee oplossingen voor alle problemen in NP worden ontsloten. En als er een polynomiale-tijd-oplossing bestaat voor alle problemen in NP, dan is P = NP.

Onder computerwetenschappers is de stelling van Cook iconisch. Leslie Valiant, van Harvard, herinnerde zich op het symposium van 2019 precies waar en wanneer hij er voor het eerst van hoorde. Nadat hij zijn bachelor wiskunde had afgerond, was hij begonnen met een doctoraat in de informatica. Hoewel er cursussen en graden waren in dit jonge vakgebied, zei hij, voelde het vluchtig aan, misschien ontbrak het aan diepgaande intellectuele inhoud. Het was een ernstige zorg voor mensen die in die tijd computerwetenschappen deden, zei hij. Ze vroegen: ‘Is dit een veld? Waar gaat het heen?' Op een dag kwam Valiant Cooks krant tegen. Hij las het van de ene op de andere dag. Ik was getransformeerd, zei hij. In een oogwenk waren mijn zorgen over informatica sterk verminderd. Dit papier - voor mij maakte het echt het veld. Ik denk dat het computerwetenschap heeft gemaakt - iets substantieels heeft gemaakt.

En toen, zoals het verhaal gaat, kwam er na de stelling van Cook een zondvloed.

In 1972 toonde Dick Karp, een computerwetenschapper in Berkeley, na het lezen van Cook's esoterische paper, aan dat veel van de klassieke computerproblemen waarmee hij goed bekend was - in wezen elk probleem dat hij niet wist op te lossen, ontleend aan wiskundige programmering, operationeel onderzoek, grafentheorie, combinatoriek en computationele logica - bezaten dezelfde transformationele eigenschap die Cook had gevonden met het vervulbaarheidsprobleem. In totaal vond Karp 21 problemen, waaronder het rugzakprobleem (zoeken naar de optimale manier om een ​​beperkte ruimte in te pakken met de meest waardevolle items), het handelsreizigersprobleem (het vinden van de kortst mogelijke route die elke stad één keer aandoet en terugkeert naar de stad van oorsprong), en het Steinerboomprobleem (streven naar een optimale verbinding van een reeks punten met lijnstukken met een minimale totale lengte).

Karp toonde aan dat deze speciale verzameling problemen allemaal gelijkwaardig waren, wat op zijn beurt aantoonde dat het patroon dat door Cook werd geïdentificeerd geen geïsoleerd fenomeen was, maar eerder een classificatiemethodologie van verrassende kracht en reikwijdte. Het was een soort lakmoesproef, het identificeren van de klasse van wat bekend werd als NP-complete problemen: een oplossing voor elke zou ze allemaal kraken.

Papadimitriou beschouwt NP-volledigheid als een veelzijdig hulpmiddel. Als je een probleem niet kunt oplossen, probeer dan te bewijzen dat het NP-compleet is, want dit zal je misschien veel tijd besparen, zei hij tijdens de openbare lezing - je kunt een exacte oplossing opgeven en doorgaan met het oplossen van een benadering of variatie van het probleem in plaats daarvan.

In de grote geschiedenis ziet Papadimitriou het fenomeen van NP-volledigheid en de P vs. NP-zoektocht als het lot van de computerwetenschap. Want zoals wetenschappelijke serendipiteit het zou willen hebben, kwam een ​​Sovjet-wiskundige, Leonid Levin, min of meer tegelijkertijd tot een resultaat dat equivalent was aan dat van Cook. Levin, nu aan de Boston University, deed zijn werk achter het IJzeren Gordijn. Nadat het meer aandacht kreeg (hij emigreerde in 1978 naar Amerika), werd het resultaat bekend als de stelling van Cook-Levin.

En in nog een coda, ongeveer tien jaar later, werd een verloren brief ontdekt in de Princeton-archieven van de Oostenrijkse logicus Kurt Gödel. In 1956 had hij Von Neumann geschreven met de vraag of een logisch probleem - dat in het moderne spraakgebruik NP-compleet zou worden genoemd - in polynomiale tijd kon worden opgelost. Hij meende dat dit gevolgen van de grootste omvang zou hebben.

Het kliekprobleem: zoek naar kliekjes in een grafiek, zoals een bepaalde subset van vrienden in een sociaal netwerk.

DEREK BRAHNEY

Vier. Hoewel een halve eeuw werk niets in de buurt van een oplossing heeft opgeleverd, spreken sommige resultaten in ieder geval tot de verbeelding: een paper in 2004 claimde een bewijs voor P = NP met zeepbellen als een mechanisme voor analoge berekening (zeepfilm, natuurlijk uitlijning in de configuratie met minimale energie, lost het NP-complete Steiner-boomprobleem op een bepaalde manier op).

Tegenwoordig is het een zeldzame vogel van een computerwetenschapper - bijvoorbeeld Ron Fagin, een IBM-collega - die het probleem direct aanpakt. In de jaren zeventig produceerde hij de stelling van Fagin, die de klasse NP kenmerkte in termen van wiskundige logica. En hij heeft het probleem meer dan eens opgelost, maar de resultaten bleven nooit langer dan een paar dagen staan ​​voordat hij een bug vond. Fagin kreeg onlangs financiering voor een P vs. NP-project van IBM's Exploratory Challenges-programma ter ondersteuning van avontuurlijk onderzoek. Om uit te leggen waarom hij het volhoudt, citeert hij graag Theodore Roosevelt, die zei dat het veel beter is om machtige dingen te wagen dan te behoren tot degenen die in een grijze schemering leven die noch overwinning noch nederlaag kent.

Maar de meeste complexiteitstheoretici dromen een beetje kleiner en kiezen in plaats daarvan voor indirecte benaderingen - het probleem kantelen, hervormen of herkaderen, gerelateerde omgevingen verkennen en het arsenaal aan hulpmiddelen dat ertegen kan worden ingezet verder verkleinen (velen zijn nu bekend als nutteloos ).

Ryan Williams, een computerwetenschapper aan het MIT, probeert het probleem zowel van bovenaf als van onderaf te belichten - door de aard van boven- en ondergrenzen te onderzoeken bij de belangrijkste rekenproblemen. Een bovengrens, in eenvoudige bewoordingen, is een specifieke wiskundige bewering dat er een concreet algoritme bestaat dat een bepaald probleem oplost zonder een bepaalde hoeveelheid middelen (tijd, geheugen, energie) te overschrijden. Een ondergrens is het ongrijpbare tegenovergestelde: het is een algemene claim van onmogelijkheid, die aantoont dat een dergelijk algoritme niet universeel bestaat. Een van de aandachtspunten van Williams' onderzoek is het maken van ondergrenzen constructieve en concrete-wiskundige objecten met beschrijfbare kenmerken. Hij is van mening dat meer constructieve benaderingen van ondergrenzen precies zijn wat we missen in de huidige benaderingen in de complexiteitstheorie.

Williams heeft de kans dat P ≠ NP vastgepend op een redelijk gematigde 80%. Maar de laatste tijd uiten sommige onderzoekers in het veld twijfels over zelfs die mate van zekerheid. Ik begin me steeds meer af te vragen of P gelijk is aan NP, zegt Toniann Pitassi, computerwetenschapper aan de Universiteit van Toronto en voormalig PhD-student van Cook. Haar benadering bij het cirkelen rond het probleem is het bestuderen van zowel opgeschaalde als verkleinde analogen, hardere en gemakkelijkere modellen. Soms maakt het veralgemenen van de vraag het duidelijker, zegt ze. Maar over het algemeen heeft ze geen duidelijkheid gekregen: de meeste mensen denken dat P niet gelijk is aan NP. En ik weet het niet. Misschien ligt het aan mij, maar ik heb het gevoel dat het steeds minder duidelijk wordt dat dat de waarheid is.

Pitassi wijst erop dat historisch gezien verrassende resultaten uit het niets zijn gekomen - schijnbare onmogelijkheden die mogelijk zijn gebleken door slimme algoritmeontwerpers. Hetzelfde kan gebeuren met P vs. NP, misschien over nog eens 50 jaar of een eeuw. Een van de belangrijkste resultaten in de hele complexiteitstheorie werd bijvoorbeeld bereikt door David Barrington, van de Universiteit van Massachusetts, Amherst, in 1989. De kern ervan (voor onze doeleinden) is dat hij een slim algoritme bedacht, dat wilde iets doen waarvoor schijnbaar een onbeperkte hoeveelheid geheugen nodig was, maar dat in feite een verbazingwekkend kleine hoeveelheid gebruikte - slechts vijf bits informatie, genoeg om een ​​getal tussen één en 32 (inclusief) of een woord van twee letters te specificeren.

Een recenter en gerelateerd resultaat, uit 2014, verraste James Cook. Puttend uit de stelling van Barrington, gebruikt het geheugen op een wonderbaarlijk vreemde manier. Zoals gesuggereerd in de titel van het artikel, door Harry Buhrman en medewerkers van de Universiteit van Amsterdam, gaat het over computers met een volledig geheugen. James kan de inleidende paragraaf van de krant praktisch letterlijk afpraten:

Stel je het volgende scenario voor. U wilt een berekening uitvoeren waarvoor meer geheugen nodig is dan u momenteel op uw computer heeft. Een manier om met dit probleem om te gaan, is door een nieuwe harde schijf te installeren. Het blijkt dat je een harde schijf hebt, maar deze staat vol met gegevens, afbeeldingen, films, bestanden, enz. Je hebt momenteel geen toegang tot die gegevens, maar je wilt deze ook niet wissen. Kunt u de harde schijf gebruiken voor uw berekening, waarbij u mogelijk de inhoud tijdelijk wijzigt, om te garanderen dat wanneer de berekening is voltooid, de harde schijf weer in zijn oorspronkelijke staat is met alle gegevens intact?

Het antwoord, contra-intuïtief, is ja.

James beschouwt het als een geleende herinnering. Nadat de schok van dit resultaat tot hem doordrong, vond hij het leuk om uit te zoeken hoe hij het op een bepaald probleem kon toepassen: verdergaan waar zijn vader was gebleven.

Een paar decennia geleden ging Steve Cook verder met andere gerelateerde problemen in de complexiteitstheorie. Met één probleem deed hij een vermoeden over de hoeveelheid geheugen die een algoritme nodig zou hebben om het probleem op te lossen - tot het absolute minimum. In 2019 zette James samen met Ian Mertz, een van Pitassi’s PhD-studenten, het poëtische idee van geheugen lenen in en bewees dat er nog minder geheugen nodig was. Het resultaat ging niet helemaal om het vermoeden van zijn vader te weerleggen, maar het is toch een beetje vooruitgang in de grote zoektocht naar complexiteit.

En problemen in de complexiteitstheorie, merkt James op, hebben soms een domino-effect: als er een bewijs is in een kritieke hoek, dan vallen alle dominostenen. De baanbrekende resultaten, de belangrijkste, komen van een lange reeks werk, door veel verschillende mensen, die stapsgewijze vooruitgang boeken en verbanden leggen tussen verschillende vragen, totdat er uiteindelijk een groot resultaat naar voren komt.

Hij maakt ook een waarschuwing: terwijl een werkelijk duivels snel P = NP-algoritme wereldschokkend zou zijn, is er ook een scenario waarin P = NP een teleurstelling zou kunnen zijn. Het zou kunnen blijken dat een P-algoritme dat in staat is om het NP-volledige probleem op te lossen, zich op een tijdschaal bevindt van, laten we zeggen, N ^100. Technisch valt dat onder P: het is een polynoom, zegt James. Maar N ^ 100 is nog steeds erg onpraktisch - het zou betekenen dat grote problemen nog steeds buiten bereik zijn op menselijke tijdschalen.

Dat is natuurlijk ervan uitgaande dat we het algoritme in de eerste plaats kunnen vinden. Donald Knuth, een algoritmist bij Stanford, is de afgelopen jaren van gedachten veranderd - hij heeft het roer omgedraaid. Zijn intuïtie is dat P inderdaad gelijk is aan NP, maar dat we dat feit praktisch gezien waarschijnlijk nooit zullen kunnen gebruiken - omdat we eigenlijk geen van de algoritmen kennen die toevallig werken. Er zijn verbijsterende aantallen algoritmen, legt hij uit, maar de meeste liggen buiten ons bereik. Dus terwijl sommige onderzoekers volhouden dat er geen P = NP-algoritme bestaat, stelt Knuth dat het waarschijnlijker is dat er nooit een polynomiaal-tijd-algoritme zal worden belichaamd - feitelijk opgeschreven als een programma - door gewone stervelingen.

Voor Papadimitriou zou elk antwoord een levenslange obsessie uitdoven. Hij gelooft dat het P vs. NP-probleem thuishoort in het domein van fundamentele wetenschappelijke raadsels zoals het ontstaan ​​van leven en de eenwording van de krachtvelden van de natuur. Het is het soort diepgaande, consequente puzzel, concreet en toch universeel, zei hij, die niet alleen betekenis geeft aan de wetenschap, maar ook aan het menselijk leven zelf.

Stel je voor dat we geluk hebben en dat we in staat zijn om nog een paar duizend jaar uit deze planeet te persen, tegen de verwachtingen in en ondanks de rare snuiters, zei hij. En wij lossen deze problemen niet op. Wat is het punt?!