AI kan ha knäckt 25 år gammal datavetenskaplig hypotes

En av teoretisk datavetenskaps mest etablerade antaganden kan ha fått sig en rejäl törn.

OpenAI meddelade den 26 oktober att företagets AI-system hade hittat ett resultat som enligt bolaget visar att Exponential Time Hypothesis, ETH, är falsk. Hypotesen har funnits sedan slutet av 1990-talet och används i hundratals forskningsarbeten för att resonera om hur svåra vissa beräkningsproblem är.

Kort därefter publicerade Anthropic ett eget AI-genererat resultat som också uppges motbevisa ETH, rapporterar TechCrunch. Båda företagens resultat granskas nu av forskare utanför bolagen.

Läs även: OpenAI utmanar Meta med AI-assistenten Dots

AI hittade snabbare sätt att lösa svåra problem

ETH handlar förenklat om hur snabbt datorer kan lösa vissa mycket svåra logiska problem.

Ett centralt exempel är SAT-problem, där en dator ska avgöra om det går att tilldela värden till ett antal variabler så att en logisk formel blir sann. När antalet variabler växer blir antalet möjliga kombinationer snabbt enormt.

ETH säger i praktiken att det inte finns någon generell metod som löser vissa sådana problem i så kallad subexponentiell tid.

OpenAI hävdar nu att företagets AI har hittat just en sådan metod.

Enligt företagets tekniska material kan algoritmen lösa vissa varianter av SAT-problemet snabbare än vad ETH tillåter. Resultatet formaliserades dessutom i bevisverktyget Lean, som används för att maskinellt kontrollera matematiska bevis.

OpenAI uppger att AI-systemet först hittade sitt bevis den 16 oktober och att en formell Lean-version färdigställdes dagen därpå.

Betyder inte att P mot NP är löst

Resultatet har väckt stor uppmärksamhet eftersom ETH ligger nära ett ännu större problem inom datavetenskap: P mot NP.

Frågan handlar i grova drag om huruvida problem som är snabba att kontrollera också kan vara snabba att lösa.

Ett vanligt exempel är sudoku. Det är enkelt att kontrollera att en färdig lösning stämmer, men betydligt svårare att hitta lösningen från början.

Om P skulle visa sig vara lika med NP skulle många problem som i dag anses extremt svåra plötsligt kunna lösas mycket snabbare än väntat.

Det är däremot inte vad OpenAI eller Anthropic har bevisat.

MIT-professorn Ryan Williams, som är med och organiserar den externa granskningen, säger till TechCrunch att resultatet kan få forskare att ge något större sannolikhet åt möjligheten att P är lika med NP. Men det löser inte själva frågan.

Läs även: Anthropic vinner tung seger mot Trump

Resultatet granskas fortfarande

OpenAI har satt samman en extern grupp ledd av Russell Impagliazzo, Ramamohan Paturi och Ryan Williams.

Impagliazzo och Paturi var med och formulerade ETH, vilket gör dem särskilt relevanta för granskningen.

OpenAI har dessutom publicerat både den AI-genererade texten och det formella Lean-beviset för att andra forskare ska kunna kontrollera arbetet. Företaget säger också att det ska finansiera en konferens där forskarsamhället kan diskutera resultaten och konsekvenserna.

Williams säger till TechCrunch att vissa delar av OpenAI-beviset ser relativt rutinmässiga ut, medan andra delar är betydligt mer oväntade och kräver närmare analys.

Han beskriver några delar som nästan främmande i sitt upplägg och menar att hela forskarsamhället behöver hjälpa till att förstå vad resultatet faktiskt innebär.

Även säkerhetsfrågan har redan kommit upp.

Snabbare algoritmer för vissa svåra problem kan i teorin påverka kryptografi, men enligt Williams har OpenAI gjort analyser och bedömer i nuläget att resultatet inte innebär att dagens kryptografiska system plötsligt har blivit osäkra.

Om bevisen håller kan konsekvenserna ändå bli stora.

ETH har under många år använts som grund för att visa att olika problem sannolikt inte kan lösas mycket snabbare. Om hypotesen faktiskt är falsk kan hundratals tidigare forskningsresultat behöva granskas på nytt.

Och kanske minst lika viktigt: ett av de mest uppmärksammade resultaten inom teoretisk datavetenskap på länge kan då ha hittats av AI.