Een OpenAI-model heeft de Exponential Time Hypothesis (ETH) weerlegd door een snellere methode te vinden voor een klassiek logisch raadsel. Een machine-gecontroleerd bewijs ondersteunt deze claim en zet daarmee een aanname op zijn kop waar onderzoekers 27 jaar lang op vertrouwden.
Dit resultaat bewijst niet dat P gelijk is aan NP, de grotere vraag achter moderne encryptie. Daarom vormt het algoritme geen direct gevaar voor de cryptografie die Bitcoin (BTC) en Ethereum beveiligt.
Waarom was de Exponential Time Hypothesis belangrijk
De hypothese draait om 3-SAT, een puzzel met waar-of-nietwaar-schakelaars en regels die ze verbinden. Het doel is om een stand van de schakelaars te vinden die aan alle regels tegelijk voldoet.
Het controleren van een voorgesteld antwoord is makkelijk. Er één vinden is lastig, want met elke extra schakelaar verdubbelt het aantal mogelijke combinaties.
Russell Impagliazzo en Ramamohan Paturi stelden ETH voor in 1999. Ondanks dezelfde afkorting heeft het niets te maken met de ticker van Ethereum.
De hypothese stelt dat geen enkel algoritme deze exponentiële groei in het slechtste geval kan ontwijken.
Onderzoekers zagen het als een dragende muur. Volgens OpenAI zijn er honderden papers in de grafentheorie, computationele biologie en databases die hun moeilijkheidsresultaten hierop hebben gebaseerd.
Hoe vond een AI een kortere route die experts misten
Het systeem van OpenAI produceerde op 16 oktober een bewijs in gewone taal. Een dag later formaliseerde het team dit in Lean, software die elke logische stap controleert.
Het gepubliceerde algoritme verwerkt invoer met n variabelen in ongeveer 2^(n/√log n) stappen. Dat is sneller dan de exponentiële ondergrens die ETH voorspelde, maar nog steeds te traag voor praktisch gebruik.
OpenAI waarschuwt dat echte snelheidswinst veel meer onderzoek vereist.
Impagliazzo en Paturi, beiden aan UC San Diego, zullen nu samen met MIT’s Ryan Williams het bewijs beoordelen. Met andere woorden, de auteurs van de hypothese toetsen nu zelf de weerlegging ervan.
Ondertussen claimt OpenAI geen wetenschappelijke eer voor deze ontdekking, een houding die volgt na een eerdere Navier-Stokes-discussie.
Scott Aaronson, hoogleraar informatica aan de University of Texas in Austin, vertelde hoe hij het nieuws hoorde.
“Mijn studenten kwamen net naar mijn kantoor om te vertellen dat een OpenAI-model nu de Exponential Time Hypothesis heeft weerlegd.”
Scott Aaronson via Shtetl-Optimized
Betekent het weerleggen van ETH dat P gelijk is aan NP
Nee. P versus NP vraagt of elk probleem met snel te controleren antwoorden ook snel opgelost kan worden.
ETH was een strengere bewering dan P ≠ NP. Dus het weerleggen ervan laat de grote vraag nog steeds open.
Denk aan een berg tussen twee valleien. De AI vond een korter pad over de bergkam, niet een tunnel erdoorheen.
Greg Brockman, president en medeoprichter van OpenAI, benadrukte hetzelfde punt enkele uren na de aankondiging.
Het verschil is belangrijk voor crypto-houders. Bitcoin-handtekeningen zijn gebaseerd op elliptische krommencryptografie, een moeilijk wiskundig probleem waar dit algoritme niets aan verandert.
Benjamin Cowen, lid van de Market Intelligence Expert Council van BeInCrypto, gaat in op de bezorgdheid.
Maar om duidelijk te zijn, het weerleggen van de Exponential Time Hypothesis bewijst niet dat P = NP, en het betekent ook niet dat Bitcoin of Ethereum nu onveilig zijn.
Exponential Time Hypothesis: wat gebeurt er als machines hun makers inhalen
Overtuigingen over onmogelijkheid zijn eerder ingestort. In 1960 weerlegde Anatoly Karatsuba het vermenigvuldigingsvermoeden van Andrey Kolmogorov in ongeveer een week.
Op dezelfde manier probeerde Volker Strassen in 1969 te bewijzen dat standaard matrixvermenigvuldiging optimaal was, maar vond zelf een snellere methode.
Wat nu anders is: machines vinden de kortere route, terwijl mensen proberen het bewijs te begrijpen.
In hetzelfde rapport werden meer bewijzen in harmonische analyse en deeltjesfysica genoemd.
Die snelheid heeft gevolgen voor digitale assets. Cryptograaf Matthew Green waarschuwde al dat AI de wiskunde achter wallets zou kunnen verzwakken.
Cowen gaf aan wat dit betekent voor de markt. Volgens hem kunnen gebieden die ver van financiën afstaan, uiteindelijk toch markten veranderen.
Voor een industrie die vertrouwt op aannames over moeilijkheid, is elke AI-doorbraak nu ook meteen een stresstest.
