AI weerlegt dertig jaar oude wiskundige aanname uit de informatica

In dit artikel:

OpenAI zegt dat zijn AI-modellen een algoritme hebben ontwikkeld dat de exponentiële-tijd-hypothese (ETH) weerlegt. Die bijna dertig jaar oude hypothese geldt als een fundament van de informatica en stelt dat de benodigde rekentijd voor bepaalde logische puzzels exponentieel toeneemt als de puzzels groter worden. Volgens de ETH kunnen slimme methoden die groei niet structureel doorbreken.

De claim, die OpenAI op 26 oktober bekendmaakte, heeft tot verbazing geleid bij wetenschappers. Als het resultaat standhoudt, moeten veel conclusies over de grenzen van algoritmen en computerberekeningen worden herzien. Het betekent echter niet automatisch dat de vraag P versus NP – of snel controleerbare oplossingen ook snel te vinden zijn – positief is beantwoord.

OpenAI zegt het bewijs met de verificatiesoftware Lean te hebben gecontroleerd. Onderzoekers moeten nog vaststellen of de bewezen stelling inderdaad de betekenis heeft die OpenAI eraan geeft. Een onafhankelijke groep, met onder anderen ETH-grondleggers Russell Impagliazzo en Ramamohan Paturi, onderzoekt de claim. Zij noemen de mogelijke gevolgen groot, maar wetenschappers waarschuwen ook voor de snelle en commerciële presentatie van AI-resultaten.

OpenAI meldde tegelijk mogelijke AI-doorbraken in de wiskunde en natuurkunde. Zo zou het model een vermoeden over de concentratie van golven hebben bewezen en aantonen dat bepaalde quantumveldentheorieën wiskundig consistent zijn. Ook die resultaten moeten nog door externe deskundigen worden beoordeeld; het natuurkundige vraagstuk rond Yang-Mills is bovendien niet volledig opgelost.