OpenAI zegt dat een kunstmatig-intelligentiemodel een manier heeft gevonden om de Exponentiële Tijdhypothese (ETH) te weerleggen, een conjectuur uit de informatica uit 1999. De claim heeft geen verbinding met Ethereum, de cryptocurrency die onder het ticker ETH handelt, of met Ethereum-medestichter Vitalik Buterin.

De aankondiging leidde desalniettemin tot grappen op Crypto Twitter. "Verdomme, algo-traders hebben $ETH net geslacht", schreef gebruiker Takumi op X, terwijl Andrew Jiang opmerkte: "Vitalik is behoorlijk stil sinds dit uitkwam."

De ETH in kwestie werd voorgesteld door informatici Russell Impagliazzo, Ramamohan Paturi en Francis Zane. Deze stelt dat het logische probleem dat bekendstaat als 3-SAT niet substantieel sneller kan worden opgelost dan door elke mogelijke combinatie van variabelen te onderzoeken. Bij 3-SAT is het doel om te bepalen of waar-of-onwaar-toewijzingen kunnen voldoen aan een verzameling regels, waarbij elke regel drie variabelen bevat.

Honderden academische papers hebben vertrouwd op de hypothese om aan te tonen dat bepaalde problemen in grafentheorie, computationele biologie, databases en geometrie niet snel kunnen worden opgelost, volgens OpenAI. Het bedrijf zei dat het weerleggen van ETH vragen opnieuw kan openstellen over hoeveel sneller die taken zouden kunnen worden opgelost en onderzoekers kan helpen bij het zoeken naar verbeterde algoritmes.

"De weerlegging van de ETH heropent vragen over hoeveel sneller deze taken zouden kunnen worden," schreef OpenAI in zijn blogpost, "en kan helpen bij het sturen van de zoektocht naar betere algoritmes."

OpenAI's 67 pagina's tellende paper, gedateerd 17 oktober en herzien op 25 oktober, beschrijft een deterministisch algoritme—een dat geen willekeur gebruikt—dat elke vervullende toewijzing voor deze puzzels telt in subexponentiële tijd. Dat betekent dat de hoeveelheid werk langzaam toeneemt dan welke exponentiële functie van het aantal variabelen. Omdat het tellen van het aantal oplossingen moeilijker is dan bepalen of er minstens één oplossing bestaat, lost het resultaat ook het beslissingsprobleem op.

OpenAI zei dat zijn AI de weerlegging ontdekte op 16 oktober en dat het resultaat op 17 oktober werd geformaliseerd in Lean, software die elke logische stap mechanisch verifieert. De paper en formalisatie zijn beschikbaar op GitHub. OpenAI zei dat dit volgde op de vrijgave van 722 wiskundige manuscripten eerder die maand, waarvan er slechts 162 een door een computer gecontroleerd hoofdresultaat bevatten. Dat machine-controleerbare formaat is wat onafhankelijke onderzoekers in staat stelt elke stap van het argument zelf te verifiëren.

Impagliazzo, Paturi en MIT-professor Ryan Williams leiden een onafhankelijk onderzoek naar de claim. In een open brief waarschuwden zij dat hun deelname niet als een onderschrijving moet worden geïnterpreteerd.

"Onze betrokkenheid moet niet worden opgevat als certificering van de claim," schreven de drie, waarbij zij toevoegden dat "een resultaat van deze betekenis zorgvuldige, onafhankelijke controle vereist en het begrip dat anderen kunnen reconstrueren, in vraag stellen en voortbouwen."

OpenAI zei dat de deelnemers geen geheimhoudingsverklaringen hebben ondertekend en zonder betaling werken. Het bedrijf stemde er ook mee in om alle ruwe gegevens te publiceren en een conferentie over het resultaat te financieren.

De praktische implicaties blijven onzeker. "Het vinden van zulke algoritmes, en het omzetten van theoretische vooruitgang in praktische verbeteringen, zal aanzienlijk verder onderzoek vereisen," schreef OpenAI. De paper zegt ook dat het resultaat niet aantoont dat elk probleem in de complexiteitsklasse NP in subexponentiële tijd kan worden opgelost.

Dat betekent dat het P versus NP-probleem onopgelost blijft. P bestaat uit problemen die computers efficiënt kunnen oplossen, terwijl NP bestaat uit problemen waarvan voorgestelde oplossingen efficiënt kunnen worden gecontroleerd. De onopgeloste vraag is of elk probleem waarvan het antwoord efficiënt kan worden gecontroleerd ook efficiënt kan worden opgelost.

Anthropic trad op 26 oktober toe tot de discussie met een paper die wordt toegeschreven aan Claude en getiteld "A 2^o(n) Time Algorithm for 3-SAT." De repository, die ook het ETH-probleem behandelt, zegt dat een intern onderzoekmodel van Claude het algoritme ontdekte. Eraan wordt toegevoegd dat "het resultaat puur asymptotisch is en niets zegt over het oplossen van formules in de praktijk."

Claude formaliseerde de Grote Stelling van Fermat in Lean in september. Wiskundige Terence Tao had gewaarschuwd voor de mogelijkheid van overlappende AI-inspanningen en schreef in september: "We hebben nu gezien dat zelfs het gerucht dat iemand aan een probleem werkt een enorme hoeveelheid AI-aangedreven inspanning kan triggeren om het plat te gooien voordat het oorspronkelijke onderzoeksproject de tijd heeft gehad zijn volledige potentieel te bereiken."

OpenAI's recente bijdrage van $5 miljoen aan de Simons Foundation zal workshops, conferenties en speciale programma's ondersteunen die bedoeld zijn om onderzoekers te helpen resultaten geproduceerd met AI te onderzoeken en daarop voort te bouwen.

Bron: Decrypt