OpenAI és Anthropic cáfolta az exponenciális idő hipotézisét

Az OpenAI és az Anthropic is azt állította, hogy cáfolta az exponenciális idő hipotézist (ETH). Az elmúlt 27 évben ez a feltevés számos elméleti informatikai kutatás alapja volt a számítási komplexitás és az algoritmustervezés területén, mivel azt feltételezte, hogy bizonyos problémák megoldásához szükséges idő a probléma méretével exponenciálisan nő.

A cégek a bizonyításokat természetes nyelven és a gépileg ellenőrizhető Lean formátumban is közzétették a GitHubon. A kutatók még nem ellenőrizték függetlenül, és nem volt idejük teljesen megérteni azokat. Az OpenAI felkérte a hipotézist eredetileg megfogalmazó, kaliforniai UC Santa Barbara-i informatikusokat és egy MIT-es akadémikust, hogy segítsenek a bizonyítások értelmezésében. Az erre irányuló munkához egy Google-űrlap is tartozik önkénteseknek és visszajelzéseknek, az OpenAI pedig egy, a témának szentelt konferencia finanszírozását vállalta.

Daniel Lokshtanov, az UC Santa Barbara professzora szerint, ha az eredmény megerősítést nyer, mintegy 50 általa publikált cikk válik értelmetlenné vagy átdolgozásra szorul. Thore Husfeldt, a koppenhágai IT Egyetem algoritmuskutató csoportjának vezetője az eredményt fantasztikusnak nevezte, Victor Lagerkvist, a Linköpingi Egyetem docense pedig azt mondta, visszatér olyan problémákhoz, amelyeket korábban az ETH igazsága miatt feladott. Lokshtanov szerint az eredmény közvetlenül nem érinti a kriptográfiát, de egyes kriptorendszer-tervezőket valószínűleg meg kell rémisztenie.