AI weerlegt de exponentiële-tijdhypothese: wat dit allemaal betekent

OpenAI en Anthropic publiceerden elk een bewijs dat de exponentiële-tijdhypothese onwaar is.

ETH is een 27 jaar oude aanname in de theoretische informatica die stelt dat sommige problemen nooit veel sneller op te lossen zijn dan met brute force. Nu zeggen de toonaangevende AI-labs dat dat simpelweg niet klopt.

Als de bewijzen standhouden, zijn dit de meest significante door AI gegenereerde resultaten in de informatica tot nu toe. Ze dwingen ook tot heroverweging van letterlijk honderden onderzoeksartikelen die ervan uitgingen dat ETH waar is.

In dit artikel leggen we uit wat de exponentiële-tijdhypothese precies betekent, samen met P vs. NP, waarmee het verwant is. We bekijken ook wat de twee labs precies beweren, hoe de bewijzen zijn gecontroleerd en wat er wel (en niet) verandert voor cryptografie.

P vs. NP in eenvoudige taal

P versus NP vraagt of elk probleem waarvan een antwoord makkelijk te controleren is, ook makkelijk op te lossen is. Het is een van de zeven Millenniumprijsproblemen en blijft ook na dit nieuws onopgelost.

Een Sudoku-puzzel is de klassieke illustratie. Een ingevuld rooster controleren kost seconden: scan elke rij, kolom en box op herhalingen. De oplossing vinden vanuit een grotendeels leeg rooster kan veel langer duren, en het verschil explodeert naarmate het rooster groeit.

• P is de klasse problemen die een computer kan oplossen in polynomiale tijd, wat betekent dat de benodigde arbeid groeit als n^², n^³, enzovoort naarmate de invoergrootte n toeneemt.
• NP is de klasse problemen waarvan voorgestelde oplossingen een computer in polynomiale tijd kan verifiëren.

Elk probleem in P zit ook in NP. De open vraag is of het omgekeerde geldt. De meeste informatici geloven dat P ≠ NP, zodat sommige problemen fundamenteel moeilijker zijn om op te lossen dan om te controleren. Moderne cryptografie leunt op dat geloof: versleutelen is makkelijk, maar ontsleutelen zonder sleutel hoort moeilijk te zijn.

Wat is de exponentiële-tijdhypothese?

ETH is scherper: het stelt dat één specifiek NP-probleem, 3-SAT, exponentiële tijd nodig heeft, hoe slim het algoritme ook is. Russell Impagliazzo en Ramamohan Paturi van UC San Diego stelden het eind jaren 90 voor, met Francis Zane als bijdrager aan het funderende werk.

Het 3-SAT-probleem

Bij 3-SAT krijg je een formule bestaande uit n waar/onwaar-variabelen en een lijst met clausules. Elke clausule verbindt drie voorwaarden met OF, bijvoorbeeld "x₁ is waar OF x₄ is onwaar OF x₇ is waar." De taak is om een instelling van de variabelen te vinden die alle clausules tegelijk voldoet.

Brute force probeert alle 2ⁿ instellingen, dus elke extra variabele verdubbelt het werk. Je ziet dat dit rond 100 variabelen uitzichtloos wordt.

Wat ETH zegt

ETH stelt dat er een constante c > 1 is zodanig dat geen enkel algoritme 3-SAT sneller oplost dan cⁿ. Sluwe algoritmen kunnen de basis onder 2 krijgen, maar nooit helemaal omlaag naar iets subexponentieels. Formeel: er bestaat δ > 0 zodanig dat 3-SAT niet kan worden opgelost in tijd O(2^δn).

Decennialang paste de voortgang in dat plaatje. Onderzoekers bleven de basis verkleinen, maar die bleef ruim boven 1. Omdat 3-SAT naar veel andere problemen kan worden omgezet, werd ETH een werkpaard-aanname. Onderzoekers gebruikten het om te beweren dat problemen als Clique, Vertex Cover, Independent Set en andere ook niet veel sneller op te lossen zijn. 

Hoe het nieuwe resultaat zich verhoudt

De nieuwe bovengrens wordt kortweg geschreven als 2^o(n). De kosten per extra variabele krimpen richting 1 naarmate n groeit, precies wat ETH onmogelijk achtte.

Wat OpenAI en Anthropic aankondigden

Beide labs bereikten in wezen dezelfde subexponentiële bovengrens onafhankelijk van elkaar, en beide ondersteunden hun papers met machinaal gecontroleerde bewijzen in de proof assistant Lean.

Anthropic zegt dat Claude het kernalgoritme zonder menselijke input vond na het produceren van zo'n 14 miljoen tokens aan output. De methode gebruikt tensornetwerken en rangargumenten. Onderzoekers hielpen daarna met de definitieve paper.

Waarom vonden beide labs het op dezelfde dag?

Geen van beide labs heeft de timing verklaard. In de paper van Anthropic worden de twee resultaten onafhankelijk en gelijktijdig genoemd, en de twee uitwerkingen volgen verschillende routes door de wiskunde om in wezen dezelfde bovengrens te bereiken. 

Enige context maakt de overlap minder verrassend dan het lijkt. Beide labs hebben hun modellen op lange lijsten met open problemen gericht, en OpenAI alleen al publiceerde honderden door AI gegenereerde wiskundige manuscripten begin oktober. ETH is een van de bekendste doelen in het veld, en beide modellen hebben geleerd van hetzelfde gepubliceerde onderzoek. Onafhankelijke, gelijktijdige ontdekkingen zijn ook een oud patroon in de wetenschap, zoals bij Newton en Leibniz voor de calculus of Darwin en Wallace voor natuurlijke selectie.

Hoe solide zijn de bewijzen?

Lean bevestigt dat een formele stelling logisch volgt uit zijn axioma's. Het kan niet bevestigen dat de formele stelling hetzelfde zegt als de paper. Anthropic merkt op dat geen enkele machine deze overeenkomst controleert, en OpenAI zegt dat zijn Lean-bestand een iets zwakkere bovengrens bewijst dan de kop claimt.

Nu organiseren dezelfde onderzoekers die het probleem voorstelden, Impagliazzo en Paturi, samen met MIT's Ryan Williams, workshops om te beoordelen of de formele stellingen ETH echt dekken. Hun brief benadrukt dat deelname aan de review geen endorsing is. Op het moment van schrijven had nog niemand publiekelijk een fout gevonden. 

Williams heeft gezegd dat delen van OpenAI's bewijs routineus lijken, terwijl "twee of drie buitenaards ogende delen" nog nauwkeurig moeten worden bekeken. Impagliazzo, een van de auteurs van ETH, noemde het resultaat diep verrassend.

Wat verandert er wel en niet

In de praktijk verandert er vandaag vrijwel niets (pfoe): de nieuwe algoritmen verslaan brute force alleen op invoer die veel groter is dan wat een computer ooit kan bevatten.

Geen snellere SAT-oplossers

De paper van Anthropic zegt dat de methode brute force alleen verslaat bij astronomisch grote invoer. Voor typische formules met vijf clausules per variabele ligt het omslagpunt bij een getal met ongeveer 10.000 cijfers. In het meest algemene geval is het een getal met grofweg 100 miljoen cijfers. 

De auteurs zeggen ook dat hun aanpak waarschijnlijk niet helpt bij iets onder zo'n 10 miljoen variabelen. De SAT-oplossers die worden gebruikt in chipverificatie, planning en resourceplanning worden hier niet sneller van.

Cryptografie is niet gebroken

Het resultaat raakt P vs NP niet. Niemand beweert dat. OpenAI zegt te hebben gecontroleerd of het algoritme echte cryptosystemen breekt en is er vrij zeker van dat dat niet zo is. 

Theorie wordt herschreven

De grotere impact zit in onderzoek. Moeilijkheidsresultaten die op ETH of SETH zijn gebouwd, hebben nu een nieuwe basis nodig, en sommige onderzoekers hebben gezegd dat jaren van hun werk mogelijk herzien moeten worden. Niet alles valt echter om. Anthropic merkt op dat het resultaat het orthogonale-vectorenprobleem niet weerlegt, dat veel fijnmazige complexiteitsresultaten ondersteunt. 

Waarom het belangrijk is voor AI

De kop gaat minder over 3-SAT en meer over wie het antwoord vond: twee AI-systemen hebben onafhankelijk een conjectuur omvergeworpen waar menselijke experts een generatie lang op vertrouwden.

AI als onderzoekspartner

Onderzoekers beschrijven nu dat er elke week of twee nieuwe AI-resultaten binnenkomen, die lopende projecten verstoren. Formele tools zoals Lean worden centraal, omdat ze mensen laten vertrouwen op een lang machinaal geschreven bewijs zonder elke regel opnieuw af te leiden.

Verborgen snelkoppelingen en zelfverbetering

ETH vatte de overtuiging dat sommige zoekproblemen geen slimme snelkoppeling hebben. Als die overtuiging onjuist is, kunnen andere ogenschijnlijk moeilijke problemen ook snelkoppelingen verbergen.

Ik denk aan algoritme-ontdekking als een gebied waar zulke snelkoppelingen veel kunnen uitmaken voor recursieve zelfverbetering, het idee van AI-systemen die helpen betere AI te ontwerpen. AI gebruiken om snellere algoritmen te vinden is een concreet pad daarnaartoe, al doet niets in dit resultaat dat vandaag direct.

Wat het betekent voor dataprofessionals

Voor mensen die met data bouwen, springen drie lessen eruit:

• Complexiteitstheorie is niet alleen academisch: Weten waarom een probleem NP-moeilijk is, vertelt je wanneer je moet denken aan heuristieken, benaderingen of solvers in plaats van exact zoeken.
• Verifiëren is een vaardigheid: Naarmate AI meer code en analyses genereert, is het controleren van de output (met tests, bewijzen of reproduceerbare pipelines) net zo belangrijk als het produceren ervan.
• Asymptotiek kan misleiden: Een in theorie "sneller" algoritme kan waardeloos zijn bij realistische groottes. 

Conclusie

Als de bewijzen de expertreview overleven, voegt de exponentiële-tijdhypothese zich bij het korte lijstje van wijd geloofde conjecturen die onwaar bleken (zoals Eulers som-van-machten-conjectuur). Maar P vs NP blijft open en cryptografie is voor nu veilig.

De volgende mijlpalen om in de gaten te houden zijn de reviewworkshops onder leiding van de oorspronkelijke auteurs van ETH, onafhankelijke herimplementaties van de algoritmen en of iemand de bovengrens verder aanscherpt.

Wil je de fundamenten achter verhalen zoals dit opbouwen? Bekijk onze cursussen over datastructuren en algoritmen, programmeren in Python en machine learning. Ze behandelen het Big-O-denken dat resultaten als deze leesbaar maakt.