En OpenAI-model har afvist Exponential Time Hypothesis (ETH) ved at finde en hurtigere metode til en klassisk logik-gåde. Et maskineverificeret bevis bakker påstanden op og vælter en antagelse, forskere har stolet på i 27 år.
Resultatet beviser ikke, at P er lig med NP, det større spørgsmål bag moderne kryptering. Derfor udgør algoritmen ikke nogen direkte trussel mod kryptografien, der sikrer Bitcoin (BTC) og Ethereum.
Hvorfor betød Exponential Time Hypothesis noget?
Hypotesen handler om 3-SAT, en gåde, der består af sandt/falsk-kontakter og regler, der forbinder dem. Målet er at finde en indstilling for kontakterne, der opfylder alle regler på én gang.
Det er let at tjekke et foreslået svar. Det er svært at finde et svar, fordi hver ekstra kontakt fordobler antallet af mulige kombinationer.
Russell Impagliazzo og Ramamohan Paturi foreslog ETH i 1999. Trods den fælles forkortelse har det intet med Ethereums ticker at gøre.
Hypotesen går ud på, at ingen algoritme kan undgå denne eksponentielle vækst i værste fald.
Forskere betragtede den som en bærende mur. Ifølge OpenAI bygger hundredvis af artikler inden for grafteori, beregningsbiologi og databaser deres sværhedsresultater på den.
Hvordan fandt en AI en genvej, eksperterne overså?
OpenAIs system lavede et naturligt sprog-bevis den 16. oktober. Dagen efter formaliserede holdet det i Lean, software der verificerer hvert logisk trin.
Den udgivne algoritme håndterer input med n variable på omtrent 2^(n/√log n) skridt. Det slår den eksponentielle bund ETH forudsagde, men er stadig alt for langsom til praktisk brug.
OpenAI advarer om, at reelle hastighedsforbedringer kræver meget mere research.
Impagliazzo og Paturi, begge fra UC San Diego, skal nu lede gennemgangen sammen med MIT’s Ryan Williams. Med andre ord vurderer hypotesens forfattere nu dens afvisning.
I mellemtiden påstår OpenAI ikke nogen videnskabelig ære for opdagelsen, en linje, der følger en tidligere Navier-Stokes-strid.
Scott Aaronson, professor i datalogi ved University of Texas i Austin, fortalte om, da han hørte nyheden.
“Mine studerende kom lige ind på mit kontor og fortalte mig, at en OpenAI-model nu har afvist Exponential Time Hypothesis”
Scott Aaronson via Shtetl-Optimized
Betyder det, at ETH er brudt, at P er lig med NP?
Nej. P versus NP handler om, hvorvidt alle problemer med hurtigt kontrollerbare svar også kan løses hurtigt.
ETH var en strengere påstand end P ≠ NP. Derfor efterlader dens modbevisning stadig det store spørgsmål åbent.
Forestil dig et bjerg mellem to dale. AI’en har fundet en kortere sti over højderyggen, ikke en tunnel igennem bjerget.
Greg Brockman, president og medstifter af OpenAI, sagde det samme få timer efter nyheden blev offentliggjort.
Distinktionen har betydning for krypto-ejere. Bitcoin-signaturer bygger på elliptisk kurve-kryptografi, et svært matematisk problem som denne algoritme ikke berører.
Benjamin Cowen, medlem af BeInCryptos Market Intelligence Expert Council, svarede på bekymringen.
Men for at være tydelig, så ville det at modbevise Exponential Time Hypothesis hverken bevise at P = NP eller at Bitcoin og Ethereum dermed er kompromitteret.
Exponential Time Hypothesis: Hvad sker der, når maskiner overgår deres skabere?
Troen på umuligheder er faldet før. I 1960 modbeviste Anatoly Karatsuba Andrey Kolmogorovs multiplikationsformodning på cirka en uge.
Ligeledes satte Volker Strassen sig i 1969 for at bevise, at standard matrixmultiplikation var optimal, men fandt i stedet en hurtigere metode.
Forskellen nu er, hvem der finder genvejen. Maskiner laver beviserne, mens mennesker prøver at forstå dem.
Samme udgivelse hævdede yderligere beviser inden for harmonisk analyse og partikelfysik.
Den hastighed har betydning for digitale aktiver. Kryptograf Matthew Green har allerede advaret om, at AI kan svække matematikken bag wallets.
Cowen satte det bredere perspektiv i markedsmæssige termer. Ifølge ham kan områder langt fra finans i sidste ende ændre markederne.
For en branche, der sikres af sværhedsantagelser, fungerer hvert AI-gennembrud nu også som en stresstest.
