Voor algoritmen is geheugen een veel krachtiger hulpmiddel dan tijd

De originele versie van dit verhaal verscheen in Quanta Magazine .

Op een middag in juli 2024 wilde Ryan Williams zijn ongelijk bewijzen. Twee maanden waren verstreken sinds hij een verrassende ontdekking had gedaan over de relatie tussen tijd en geheugen in computers. Het was een ruwe schets van een wiskundig bewijs dat geheugen krachtiger was dan computerwetenschappers dachten: een kleine hoeveelheid tijd zou net zo nuttig zijn als een grote hoeveelheid tijd in alle denkbare berekeningen. Dat klonk zo onwaarschijnlijk dat hij aannam dat er iets mis moest zijn, en hij legde het bewijs prompt terzijde om zich te concentreren op minder gekke ideeën. Nu had hij eindelijk tijd vrijgemaakt om de fout te vinden.

Dat is niet wat er gebeurde. Na urenlang over zijn betoog te hebben nagedacht, kon Williams geen enkele fout vinden.

"Ik dacht dat ik gek werd", zei Williams, theoretisch computerwetenschapper aan het Massachusetts Institute of Technology. Voor het eerst begon hij de mogelijkheid te overwegen dat het geheugen misschien, heel misschien, echt zo krachtig was als zijn werk suggereerde.

In de maanden die volgden, werkte hij de details verder uit, bestudeerde hij elke stap nauwkeurig en vroeg hij feedback van een handvol andere onderzoekers. In februari plaatste hij zijn bewijs eindelijk online , met brede bijval.

"Het is verbazingwekkend. Het is prachtig", zei Avi Wigderson , theoretisch computerwetenschapper aan het Institute for Advanced Study in Princeton, New Jersey. Zodra hij het nieuws hoorde, stuurde Wigderson Williams een felicitatiemail. De onderwerpregel was: "Je hebt me versteld doen staan."

Tijd en geheugen (ook wel ruimte genoemd) zijn de twee meest fundamentele bronnen in de computertechnologie: elk algoritme heeft enige tijd nodig om te draaien en vereist ruimte om gegevens op te slaan terwijl het draait. Tot nu toe hadden de enige bekende algoritmen voor het uitvoeren van bepaalde taken een hoeveelheid ruimte nodig die ongeveer evenredig was met hun looptijd, en onderzoekers gingen er lange tijd van uit dat er geen betere manier was om het te doen. Williams' bewijs legde een wiskundige procedure vast om elk algoritme – ongeacht wat het doet – om te zetten in een vorm die veel minder ruimte in beslag neemt.

Bovendien impliceert dit resultaat – een uitspraak over wat je kunt berekenen binnen een bepaalde hoeveelheid ruimte – ook een tweede resultaat, namelijk wat je niet kunt berekenen binnen een bepaalde tijd. Dit tweede resultaat is op zich niet verrassend: onderzoekers verwachtten dat het waar zou zijn, maar ze hadden geen idee hoe ze het moesten bewijzen. Williams' oplossing, gebaseerd op zijn eerste, allesomvattende resultaat, voelt bijna karikaturaal overdreven aan, vergelijkbaar met het bewijzen van de schuld van een verdachte moordenaar door een ijzersterk alibi te creëren voor iedereen op aarde. Het zou ook een nieuwe manier kunnen bieden om een van de oudste openstaande problemen in de informatica aan te pakken.

"Het is een behoorlijk verbluffend resultaat en een enorme vooruitgang", aldus Paul Beame , computerwetenschapper aan de Universiteit van Washington. "Het is iets minder verrassend dat Ryan dit doet."

Williams, 46, heeft een open, expressief gezicht en een vleugje grijs in zijn haar. Zijn kantoor, met uitzicht op de kleurrijke torenspitsen van het Stata Center van MIT, is een ander voorbeeld van creatief ruimtegebruik. Een paar yogamatten hebben een vensterbank omgetoverd tot een geïmproviseerd leeshoekje, en het bureau is weggestopt in een vreemd gevormde hoek, waardoor er ruimte is ontstaan voor een bank tegenover een groot whiteboard vol wiskundige krabbels.

MIT ligt ver van Williams' ouderlijk huis in het landelijke Alabama, waar ruimte geen gebrek was. Hij groeide op op een boerderij van 20 hectare en zag voor het eerst een computer toen hij zeven was, toen zijn moeder hem door de county reed voor een speciale academische bijles. Hij herinnerde zich dat hij gefascineerd was door een eenvoudig programma om een digitaal vuurwerk te genereren.

"Het nam een willekeurige kleur en stuurde die vanuit het midden van de monitor in een willekeurige richting," zei Williams. "Je had nooit kunnen voorspellen welke afbeelding je zou krijgen." De computerwereld leek een wilde en wonderlijke speeltuin, vol eindeloze mogelijkheden. De jonge Williams was er helemaal weg van.

"Ik schreef programma's voor mezelf, op papier, om op een toekomstige computer te draaien", zei hij. "Mijn ouders wisten niet echt wat ze met me aan moesten."

Naarmate hij ouder werd, stapte Williams over van denkbeeldige computers naar echte computers. Voor zijn laatste twee jaar van de middelbare school stapte hij over naar de Alabama School of Math and Science, een prestigieuze openbare kostschool, waar hij voor het eerst kennismaakte met de theoretische kant van de informatica.

"Ik realiseerde me dat er een grotere wereld aan dingen bestond, en dat er een manier was om wiskundig over computers na te denken," zei hij. "Dat was wat ik wilde doen."

Williams voelde zich vooral aangetrokken tot een tak van de theoretische informatica die computationele complexiteitstheorie wordt genoemd. Deze theorie behandelt de middelen (zoals tijd en ruimte) die nodig zijn om computationele problemen op te lossen, zoals het sorteren van lijsten of het ontbinden van getallen. De meeste problemen kunnen worden opgelost met veel verschillende algoritmen, elk met zijn eigen eisen aan tijd en ruimte. Complexiteitstheoretici verdelen problemen in categorieën, complexiteitsklassen genaamd, op basis van de benodigde middelen voor de beste algoritmen om ze op te lossen – dat wil zeggen, de algoritmen die het snelst werken of de minste ruimte innemen.

Maar hoe maak je de studie van rekenkracht wiskundig nauwkeurig? Je komt niet ver als je tijd en ruimte probeert te analyseren door minuten met megabytes te vergelijken. Om vooruitgang te boeken, moet je beginnen met de juiste definities.

Deze definities zijn voortgekomen uit het werk van Juris Hartmanis, een baanbrekende computerwetenschapper met ervaring in het omgaan met beperkte middelen. Hij werd geboren in 1928 in een vooraanstaande Letse familie, maar zijn jeugd werd verstoord door het uitbreken van de Tweede Wereldoorlog. De Sovjetbezettingsmacht arresteerde en executeerde zijn vader, en na de oorlog voltooide Hartmanis zijn middelbare school in een vluchtelingenkamp. Hij ging naar de universiteit, waar hij uitblonk, ook al kon hij zich geen studieboeken veroorloven.

"Ik compenseerde dit door zeer gedetailleerde aantekeningen te maken tijdens colleges", herinnerde hij zich in een interview uit 2009. "Improviseren en moeilijkheden overwinnen heeft zeker zijn voordelen." Hartmanis emigreerde in 1949 naar de Verenigde Staten en werkte een reeks losse baantjes – landbouwmachines bouwen, staal produceren en zelfs als butler – terwijl hij wiskunde studeerde aan de Universiteit van Kansas City. Hij maakte vervolgens een spectaculair succesvolle carrière in het jonge vakgebied van de theoretische informatica.

In 1960, tijdens zijn werk in het onderzoekslaboratorium van General Electric in Schenectady, New York, ontmoette Hartmanis Richard Stearns, een promovendus die een zomerstage liep. In twee baanbrekende artikelen stelden ze precieze wiskundige definities op voor tijd en ruimte. Deze definities gaven onderzoekers de taal die ze nodig hadden om de twee bronnen te vergelijken en problemen in complexiteitsklassen te verdelen.

Een van de belangrijkste klassen draagt de bescheiden naam "P". Ruwweg omvat deze alle problemen die binnen een redelijke tijd kunnen worden opgelost. Een analoge complexiteitsklasse voor ruimte heet "PSPACE".

De relatie tussen deze twee klassen is een van de centrale vragen van de complexiteitstheorie. Elk probleem in P bevindt zich ook in PSPACE, omdat snelle algoritmen simpelweg niet genoeg tijd hebben om veel ruimte in het geheugen van een computer te vullen. Als de omgekeerde bewering ook waar zou zijn, zouden de twee klassen equivalent zijn: ruimte en tijd zouden vergelijkbare rekenkracht hebben. Maar complexiteitstheoretici vermoeden dat PSPACE een veel grotere klasse is, met veel problemen die niet in P voorkomen. Met andere woorden, zij geloven dat ruimte een veel krachtigere rekenbron is dan tijd. Deze overtuiging komt voort uit het feit dat algoritmen hetzelfde kleine stukje geheugen steeds opnieuw kunnen gebruiken, terwijl tijd minder vergevingsgezind is: als het eenmaal verstreken is, kun je het niet meer terugkrijgen.

"De intuïtie is zo simpel", zei Williams. "Je kunt ruimte hergebruiken, maar je kunt tijd niet hergebruiken."

Maar intuïtie is niet goed genoeg voor complexiteitstheoretici: ze willen rigoureus bewijs. Om te bewijzen dat PSPACE groter is dan P, zouden onderzoekers moeten aantonen dat snelle algoritmen voor sommige problemen in PSPACE categorisch onmogelijk zijn. Waar zouden ze überhaupt beginnen?

Toevallig begonnen ze aan Cornell University, waar Hartmanis in 1965 naartoe verhuisde om de nieuw opgerichte afdeling computerwetenschappen te leiden. Onder zijn leiding groeide het al snel uit tot een onderzoekscentrum in complexiteitstheorie, en begin jaren zeventig gingen twee onderzoekers daar, John Hopcroft en Wolfgang Paul, op zoek naar een precieze link tussen tijd en ruimte.

Hopcroft en Paul wisten dat ze, om het P versus PSPACE-probleem op te lossen, moesten bewijzen dat je bepaalde berekeningen niet binnen een beperkte tijd kunt uitvoeren. Maar het is moeilijk om een ontkenning te bewijzen. In plaats daarvan besloten ze het probleem om te draaien en te onderzoeken wat je wel kunt doen met beperkte ruimte. Ze hoopten te bewijzen dat algoritmen met een bepaald ruimtebudget dezelfde problemen kunnen oplossen als algoritmen met een iets groter tijdbudget. Dat zou erop wijzen dat ruimte minstens iets krachtiger is dan tijd – een kleine maar noodzakelijke stap in de richting van het aantonen dat PSPACE groter is dan P.

Met dat doel voor ogen wendden ze zich tot een methode die complexiteitstheoretici simulatie noemen. Deze methode houdt in dat bestaande algoritmen worden omgezet in nieuwe die dezelfde problemen oplossen, maar met verschillende hoeveelheden ruimte en tijd. Om het basisidee te begrijpen, stel je voor dat je een snel algoritme krijgt om je boekenplank te alfabetiseren, maar dat je je boeken in tientallen kleine stapeltjes moet leggen. Misschien geef je de voorkeur aan een aanpak die minder ruimte inneemt in je appartement, zelfs als het langer duurt. Een simulatie is een wiskundige procedure die je kunt gebruiken om een geschikter algoritme te krijgen: voer het origineel in en het geeft je een nieuw algoritme dat ruimte bespaart ten koste van tijd.

Algoritmeontwerpers bestuderen deze ruimte-tijd-afwegingen al lang voor specifieke taken zoals sorteren. Maar om een algemene relatie tussen tijd en ruimte te leggen, hadden Hopcroft en Paul iets uitgebreiders nodig: een ruimtebesparende simulatieprocedure die voor elk algoritme werkt, ongeacht het probleem dat het oplost. Ze verwachtten dat deze algemeenheid een prijskaartje zou hebben. Een universele simulatie kan de details van een specifiek probleem niet uitbuiten, dus zal het waarschijnlijk niet zoveel ruimte besparen als een gespecialiseerde simulatie. Maar toen Hopcroft en Paul aan hun werk begonnen, waren er helemaal geen universele methoden bekend om ruimte te besparen. Zelfs een kleine besparing zou al vooruitgang betekenen.

De doorbraak kwam in 1975, nadat Hopcroft en Paul samenwerkten met een jonge onderzoeker genaamd Leslie Valiant . Het trio ontwikkelde een universele simulatieprocedure die altijd ruimte bespaart. Welk algoritme je er ook voor gebruikt, je krijgt een equivalent algoritme met een ruimtebudget dat iets kleiner is dan het tijdbudget van het oorspronkelijke algoritme.

"Alles wat je in zoveel tijd kunt doen, kun je ook in iets minder ruimte doen", zei Valiant. Het was de eerste grote stap in de zoektocht om ruimte en tijd met elkaar te verbinden.

Maar toen stokte de vooruitgang en begonnen complexiteitstheoretici te vermoeden dat ze op een fundamentele barrière waren gestuit. Het probleem was juist het universele karakter van de simulatie van Hopcroft, Paul en Valiant. Hoewel veel problemen met veel minder ruimte dan tijd kunnen worden opgelost, leken sommige intuïtief bijna net zoveel ruimte als tijd nodig te hebben. In dat geval zouden meer ruimte-efficiënte universele simulaties onmogelijk zijn. Paul en twee andere onderzoekers bewezen al snel dat ze inderdaad onmogelijk zijn, mits je één ogenschijnlijk voor de hand liggende aanname doet: verschillende datablokken kunnen niet tegelijkertijd dezelfde ruimte in het geheugen innemen.

“Iedereen ging ervan uit dat het niet beter kon”, aldus Wigderson.

Pauls resultaat suggereerde dat het oplossen van het P versus PSPACE-probleem zou vereisen dat simulatie volledig zou worden opgegeven ten gunste van een andere aanpak, maar niemand had goede ideeën. Dat was waar het probleem 50 jaar bleef bestaan – totdat Williams eindelijk de impasse doorbrak.

Eerst moest hij zijn studie aan de universiteit afronden.

In 1996 was het tijd voor Williams om zich aan te melden bij een universiteit. Hij wist dat het bestuderen van complexiteitstheorie hem ver van huis zou brengen, maar zijn ouders maakten hem duidelijk dat de westkust en Canada geen optie waren. Van de resterende opties sprong Cornell er voor hem uit vanwege de prominente plaats die het innam in de geschiedenis van zijn favoriete vakgebied.

"Deze man, Hartmanis, definieerde de tijd- en ruimtecomplexiteitsklassen", herinnerde hij zich dat hij dacht. "Dat was belangrijk voor mij."

Williams werd met royale financiële steun toegelaten tot Cornell en arriveerde in het najaar van 1997, vastbesloten om er alles aan te doen om zelf complexiteitstheoreticus te worden. Zijn vastberadenheid viel zijn medestudenten op.

"Hij was gewoon helemaal weg van de complexiteitstheorie", zegt Scott Aaronson , computerwetenschapper aan de Universiteit van Texas in Austin, die samenwerkte met Williams bij Cornell.

Maar in zijn tweede jaar had Williams moeite om bij te blijven met vakken die de nadruk legden op wiskundige nauwkeurigheid boven intuïtie. Nadat hij een middelmatig cijfer had gehaald voor een vak over computertheorie, raadde de docent hem aan om andere carrières te overwegen. Maar Williams gaf zijn droom niet op. Hij zette door en schreef zich in voor een theoriecursus op masterniveau, in de hoop dat een uitstekend cijfer voor het moeilijkere vak indrukwekkend zou overkomen op zijn aanmelding voor de masteropleiding. De professor die deze cursus gaf, was Hartmanis, inmiddels een oudgediende in het vakgebied.

Williams begon wekelijks naar Hartmanis' spreekuur te gaan, waar hij bijna altijd de enige student was die kwam opdagen. Zijn doorzettingsvermogen werd beloond: hij haalde een A voor het vak en Hartmanis stemde ermee in hem het volgende semester te adviseren over een onafhankelijk onderzoeksproject. Hun wekelijkse bijeenkomsten gingen door tijdens Williams' tijd op de universiteit. Hartmanis moedigde hem aan een individuele benadering van complexiteitsonderzoek te ontwikkelen en leidde hem voorzichtig weg van doodlopende wegen.

"Ik was toen enorm door hem beïnvloed", zei Williams. "Ik denk dat ik dat nu nog steeds ben."

Maar ondanks het feit dat hij een felbegeerde onderzoeksbeurs van de National Science Foundation had gekregen, werd Williams afgewezen door elk promotieprogramma waarvoor hij zich aanmeldde. Toen Hartmanis het nieuws hoorde, belde hij een collega, waarna hij Williams feliciteerde met zijn toelating tot een masteropleiding van een jaar aan Cornell. Een jaar later meldde Williams zich opnieuw aan bij verschillende promotieprogramma's, en met die extra onderzoekservaring op zak boekte hij succes.

Williams bleef tijdens zijn doctoraalstudie en de jaren daarna onderzoek doen naar complexiteitstheorie. In 2010, vier jaar na zijn doctoraat, leverde hij een mijlpaalresultaat – een kleine stap, maar de grootste in decennia – op weg naar de oplossing van de beroemdste vraag in de theoretische informatica : de aard van moeilijke problemen. Dat resultaat verstevigde Williams' reputatie en hij schreef vervolgens tientallen andere artikelen over verschillende onderwerpen binnen de complexiteitstheorie.

P versus PSPACE was daar niet een van. Williams was al gefascineerd door het probleem sinds hij er voor het eerst mee te maken kreeg op de universiteit. Hij had zijn studie informatica zelfs aangevuld met vakken als logica en filosofie, en zocht inspiratie bij andere perspectieven op tijd en ruimte, maar zonder resultaat.

"Het heeft altijd in mijn achterhoofd gezeten", zei Williams. "Ik kon er gewoon niets interessants genoeg over bedenken."

Vorig jaar kreeg hij eindelijk de kans waar hij op had gewacht.

Het verhaal van Williams' nieuwe resultaat begon met de vooruitgang in een andere vraag over geheugen in computers: welke problemen kunnen worden opgelost met extreem beperkte ruimte? In 2010 bedachten de baanbrekende complexiteitstheoreticus Stephen Cook en zijn medewerkers een taak, het zogenaamde boomevaluatieprobleem , waarvan ze bewezen dat deze onmogelijk zou zijn voor elk algoritme met een ruimtebudget onder een specifieke drempelwaarde. Maar er was een maas in de wet. Het bewijs was gebaseerd op dezelfde logische aanname die Paul en zijn collega's decennia eerder hadden gemaakt: algoritmen kunnen geen nieuwe data opslaan in een ruimte die al vol is.

Meer dan tien jaar lang probeerden complexiteitstheoretici die maas in de wet te dichten. Toen, in 2023, bliezen Cooks zoon James en een onderzoeker genaamd Ian Mertz het helemaal open en ontwikkelden ze een algoritme dat het boomevaluatieprobleem oploste met veel minder ruimte dan iedereen voor mogelijk had gehouden. Het bewijs van de oudere Cook ging ervan uit dat databits als kiezels waren die aparte plekken in het geheugen van een algoritme moesten innemen. Maar het blijkt niet de enige manier te zijn om data op te slaan. "We kunnen deze kiezels eigenlijk zien als dingen die we een beetje op elkaar kunnen drukken," zei Beame.

Het algoritme van Cook en Mertz wekte de nieuwsgierigheid van veel onderzoekers, maar het was niet duidelijk of het ook toepasbaar was buiten het probleem van de evaluatie van bomen. "Niemand zag hoe centraal het staat in de verhouding tussen tijd en ruimte zelf", aldus Wigderson.

Ryan Williams was de uitzondering. In het voorjaar van 2024 gaf een groep studenten een presentatie over het artikel van Cook en Mertz als hun afstudeerproject in een les die hij gaf. Hun enthousiasme inspireerde hem om er eens goed naar te kijken. Zodra hij dat deed, sprong er een idee in hem op. De methode van Cook en Mertz, zo besefte hij, was eigenlijk een universeel hulpmiddel om ruimtegebruik te verminderen. Waarom zouden we die niet gebruiken voor een nieuwe universele simulatie die tijd en ruimte met elkaar verbindt – zoals die van Hopcroft, Paul en Valiant, maar dan beter?

Dat klassieke resultaat was een manier om elk algoritme met een gegeven tijdsbudget om te vormen tot een nieuw algoritme met een iets kleiner ruimtebudget. Williams zag dat een simulatie gebaseerd op squishy kiezels het ruimtegebruik van het nieuwe algoritme veel kleiner zou maken – ongeveer gelijk aan de wortel van het tijdsbudget van het oorspronkelijke algoritme. Dat nieuwe ruimte-efficiënte algoritme zou ook veel langzamer zijn, waardoor de simulatie waarschijnlijk geen praktische toepassingen zou hebben. Maar vanuit theoretisch oogpunt was het ronduit revolutionair.

Vijftig jaar lang gingen onderzoekers ervan uit dat het onmogelijk was om de universele simulatie van Hopcroft, Paul en Valiant te verbeteren. Williams' idee zou – als het werkte – hun record niet alleen breken, maar het ook breken.

"Ik dacht erover na en dacht: 'Nou, dat kan gewoon niet waar zijn'", zei Williams. Hij legde het terzijde en kwam er pas op terug op die noodlottige dag in juli, toen hij probeerde de fout in het argument te vinden, maar faalde. Nadat hij besefte dat er geen fout in zat, besteedde hij maanden aan het schrijven en herschrijven van het bewijs om het zo duidelijk mogelijk te maken.

Eind februari zette Williams eindelijk het voltooide artikel online . Cook en Mertz waren net zo verrast als iedereen. "Ik moest eerst een lange wandeling maken voordat ik iets anders kon doen," zei Mertz.

Valiant kreeg tijdens zijn ochtendrit naar het werk alvast een voorproefje van Williams' verbetering ten opzichte van zijn decennia-oude resultaat. Jarenlang gaf hij les aan Harvard University, vlakbij Williams' kantoor aan MIT. Ze hadden elkaar al eerder ontmoet, maar wisten niet dat ze in dezelfde buurt woonden totdat ze elkaar op een besneeuwde dag in februari, een paar weken voordat de uitslag openbaar werd, in de bus tegenkwamen. Williams beschreef zijn bewijs aan de geschrokken Valiant en beloofde zijn artikel op te sturen.

"Ik was enorm onder de indruk", zei Valiant. "Als je een wiskundig resultaat krijgt dat het beste is in 50 jaar, moet je wel iets goed doen."

Met zijn nieuwe simulatie had Williams een positief resultaat bewezen over de rekenkracht van ruimte: algoritmen die relatief weinig ruimte gebruiken, kunnen alle problemen oplossen die een iets grotere hoeveelheid tijd vergen. Vervolgens draaide hij dat om met slechts een paar regels wiskunde en bewees hij een negatief resultaat over de rekenkracht van tijd: ten minste een paar problemen kunnen niet worden opgelost tenzij je meer tijd dan ruimte gebruikt. Dat tweede, beperktere resultaat komt overeen met wat onderzoekers verwachtten. Het vreemde is hoe Williams daar kwam, door eerst een resultaat te bewijzen dat van toepassing is op alle algoritmen, ongeacht welke problemen ze oplossen.

"Ik kan het nog steeds niet geloven", zei Williams. "Het lijkt gewoon te mooi om waar te zijn."

In kwalitatieve termen geformuleerd, klinkt Williams' tweede resultaat misschien als de lang gezochte oplossing voor het P versus PSPACE-probleem. Het verschil is een kwestie van schaal. P en PSPACE zijn zeer brede complexiteitsklassen, terwijl Williams' resultaten op een fijner niveau werken. Hij stelde een kwantitatieve kloof vast tussen de macht van ruimte en de macht van tijd, en om te bewijzen dat PSPACE groter is dan P, zullen onderzoekers die kloof veel, veel groter moeten maken.

Dat is een enorme uitdaging, vergelijkbaar met het openbreken van een scheur in het trottoir met een koevoet tot hij zo breed is als de Grand Canyon. Maar het zou mogelijk kunnen zijn om dit te bereiken met een aangepaste versie van Williams' simulatieprocedure die de belangrijke stap vele malen herhaalt, waardoor elke keer wat ruimte wordt bespaard. Het is vergelijkbaar met een manier om de lengte van je koevoet herhaaldelijk te vergroten – maak hem groot genoeg, en je kunt alles openbreken. Die herhaalde verbetering werkt niet met de huidige versie van het algoritme, maar onderzoekers weten niet of dat een fundamentele beperking is.

"Het zou een ultiem knelpunt kunnen zijn, of een knelpunt dat vijftig jaar aanhoudt", aldus Valiant. "Of het zou iets kunnen zijn dat misschien volgende week opgelost kan worden."

Als het probleem volgende week wordt opgelost, zal Williams zich wel voor zijn kop slaan. Voordat hij het artikel schreef, heeft hij maandenlang geprobeerd zijn resultaten te verbeteren, maar het is hem niet gelukt. Maar zelfs als zo'n verbetering niet mogelijk is, heeft Williams er vertrouwen in dat verdere ruimteverkenning ongetwijfeld tot interessante resultaten zal leiden – misschien wel tot vooruitgang op het gebied van een heel ander probleem.

"Ik kan nooit precies bewijzen wat ik wil bewijzen," zei hij. "Maar vaak is wat ik bewijs veel beter dan wat ik wilde."

Opmerking van de redactie: Scott Aaronson is lid van de raad van advies van Quanta Magazine.

Oorspronkelijk verhaal met toestemming overgenomen uit Quanta Magazine , een redactioneel onafhankelijke publicatie van de Simons Foundation. De missie van deze publicatie is om het publieke begrip van wetenschap te vergroten door verslag te doen van ontwikkelingen en trends in het onderzoek naar wiskunde, natuurkunde en levenswetenschappen.