OpenAI och Anthropic publicerade var sitt bevis på att den exponentiella tidshypotesen är falsk.
ETH är ett 27 år gammalt antagande inom teoretisk datavetenskap som säger att vissa problem aldrig kan lösas mycket snabbare än med brute force. Nu menar de ledande AI-labben att det helt enkelt inte stämmer.
Om bevisen håller är de de mest betydelsefulla AI-genererade resultaten i datavetenskap hittills. De tvingar också fram en omprövning av bokstavligen hundratals forskningsartiklar som utgick från att ETH var sann.
I den här artikeln förklarar vi vad den exponentiella tidshypotesen faktiskt betyder, tillsammans med P kontra NP, som är relaterat. Vi tittar också på exakt vad de två labben hävdar, hur bevisen kontrollerades och vad som (inte) förändras för kryptografi.
P kontra NP i klartext
P kontra NP frågar om varje problem vars svar är lätt att kontrollera också är lätt att lösa. Det är ett av de sju Millenniumprisen-problemen, och det är fortfarande olöst efter denna nyhet.
Sudoku är det klassiska exemplet. Att kontrollera ett ifyllt rutnät tar sekunder: skanna varje rad, kolumn och ruta efter upprepningar. Att hitta lösningen från ett i stort sett tomt rutnät kan ta mycket längre tid, och gapet exploderar när rutnätet växer.
- P är klassen av problem som en dator kan lösa på polynomisk tid, vilket betyder att arbetet växer som n², n³ och så vidare när indata-storleken n växer.
- NP är klassen av problem vars föreslagna lösningar en dator kan verifiera på polynomisk tid.
Varje problem i P ligger också i NP. Den öppna frågan är om omvändningen gäller. De flesta datavetare tror att P ≠ NP, så att vissa problem i grunden är svårare att lösa än att kontrollera. Modern kryptografi lutar sig mot den tron: att kryptera är lätt, men att häva kryptering utan nyckel ska vara svårt.
Vad är den exponentiella tidshypotesen?
ETH är skarpare: den hävdar att ett specifikt NP-problem, 3-SAT, kräver exponentiell tid oavsett hur smart algoritmen är. Russell Impagliazzo och Ramamohan Paturi vid UC San Diego föreslog den i slutet av 1990-talet, med Francis Zane som bidrog till det grundläggande arbetet.
Problemet 3-SAT
I 3-SAT får du en formel bestående av n sann/falsk-variabler och en lista av klausuler. Varje klausul fogar samman tre villkor med ELLER, till exempel ”x₁ är sann ELLER x₄ är falsk ELLER x₇ är sann.” Uppgiften är att hitta en inställning av variablerna som uppfyller alla klausuler samtidigt.
Brute force testar alla 2ⁿ inställningar, så varje extra variabel fördubblar arbetet. Du ser hur det runt 100 variabler är hopplöst.
Vad ETH säger
ETH säger att det finns en konstant c > 1 sådan att ingen algoritm löser 3-SAT snabbare än cⁿ. Smartare algoritmer kan krympa basen under 2, men aldrig hela vägen ner till något subexponentiellt. Formellt: det existerar δ > 0 sådan att 3-SAT inte kan lösas på tid O(2δn).
Under decennier stämde framstegen med den bilden. Forskare fortsatte att hyvla ner basen, men den låg långt över 1. Eftersom 3-SAT kan konverteras till många andra problem blev ETH ett arbetshypotes. Forskare använde den för att hävda att problem som Clique, Vertex Cover, Independent Set och andra inte heller kan lösas mycket snabbare.
Hur det nya resultatet står sig
| Angreppssätt | Körtid för 3-SAT | Växer exponentiellt? |
|---|
| Brute force | 2ⁿ | Ja |
| Bäst känt före okt 2026 (deterministisk) | ungefär 1,328ⁿ | Ja |
| Bäst känt före okt 2026 (slumpmässig) | ungefär 1,308ⁿ | Ja |
| OpenAI och Anthropic (okt 2026) | 2^O(n log log n / √log n) | Nej: subexponentiell |
Den nya gränsen skrivs i kortform 2o(n). Kostnaden per tillagd variabel krymper mot 1 när n växer, vilket är precis vad ETH sa var omöjligt.
Vad OpenAI och Anthropic tillkännagav
Båda labben nådde i huvudsak samma subexponentiella gräns oberoende av varandra, och båda backade upp sina artiklar med maskinkontrollerade bevis i bevisassistenterna Lean.
| | OpenAI | Anthropic |
|---|
| Artikel | "The Exponential Time Hypothesis Is False" (67 sidor) | "A 2o(n) Time Algorithm for 3-SAT" (49 sidor) |
| Modell | Nämnlös intern modell | Intern Claude-forskningsmodell, krediterad som författare |
| Kärnidén funnen | 16 oktober 2026 | 16 oktober 2026 |
| Gjord offentlig | 26 oktober 2026 | 26–27 oktober 2026 |
| Verifiering | Lean-bevis för en något svagare gräns som ändå motbevisar ETH | Lean 4-bevis mot Mathlib, omkontrollerat av en andra kärna |
| Extra påståenden | Fartökningen gäller inte hela NP | Motbevisar även starka ETH (SETH); ny kretsspärr (circuit lower bound) |
Anthropic säger att Claude hittade kärnalgoritmen utan mänsklig input efter att ha producerat cirka 14 miljoner token i output. Metoden använder tensornätverk och rangargument. Forskare hjälpte sedan till med den slutliga artikeln.
Varför hittade båda labben den samma dag?
Inget av labben har förklarat tidpunkten. Anthropics artikel kallar de två resultaten oberoende och samtidiga, och de två texterna tar olika vägar genom matematiken för att nå i huvudsak samma gräns.
Viss kontext gör överlappet mindre förvånande än det först verkar. Båda labben har riktat sina modeller mot långa listor av olösta problem, och OpenAI ensam släppte hundratals AI-genererade matematikmanuskript i början av oktober. ETH är ett av de mest kända målen i fältet, och båda modellerna lärde sig från samma publicerade forskning. Oberoende, samtidiga upptäckter är också ett gammalt mönster i vetenskapen, som med Newton och Leibniz om kalkyl eller Darwin och Wallace om naturligt urval.
Hur solida är bevisen?
Lean bekräftar att ett formellt påstående följer logiskt från dess axiom. Det kan inte bekräfta att det formella påståendet säger samma sak som artikeln. Anthropic noterar att ingen maskin kontrollerar denna överensstämmelse, och OpenAI säger att deras Lean-fil bevisar en något svagare gräns än rubriken.
Nu organiserar samma forskare som föreslog problemet, Impagliazzo och Paturi, tillsammans med MIT:s Ryan Williams, workshops för att bedöma om de formella påståendena verkligen fångar ETH. Deras brev understryker att deltagande i granskningen inte är ett godkännande. Just nu, när denna artikel skrivs, har ingen offentligt hittat ett fel.
Williams har sagt att delar av OpenAIs bevis ser rutinmässiga ut, medan ”två eller tre utomjordiskt utseende delar” fortfarande behöver noggrann granskning. Impagliazzo, en av ETH:s författare, har beskrivit resultatet som djupt överraskande.
Vad som förändras och vad som inte gör det
I praktiken förändras nästan ingenting idag (puh): de nya algoritmerna slår bara brute force på indata som är långt större än vad en dator någonsin skulle kunna rymma.
Inga snabbare SAT-lösare
Anthropics artikel säger att metoden bara slår brute force på astronomiskt stora indata. För typiska formler med fem klausuler per variabel ligger brytpunkten vid ett tal med cirka 10 000 siffror. I det mest allmänna fallet är det ett tal med ungefär 100 miljoner siffror.
Författarna säger också att deras angreppssätt sannolikt inte hjälper på något under cirka 10 miljoner variabler. De SAT-lösare som används i kretsverifiering, schemaläggning och planering blir inte snabbare av detta resultat.
Kryptografi är inte krossad
Resultatet rör inte P kontra NP. Ingen låtsas det. OpenAI säger att de kontrollerade om algoritmen bryter verkliga kryptosystem och är ganska säkra på att den inte gör det.
Teorin skrivs om
Den större effekten gäller forskningen. Svårighetsresultat som bygger på ETH eller SETH behöver nu ny grund, och vissa forskare har sagt att år av deras eget arbete kan behöva ses över. Allt faller dock inte. Anthropic noterar att resultatet inte motbevisar problemet med ortogonala vektorer, som stöder många finkorniga komplexitetsresultat.
Varför det spelar roll för AI
Rubriken handlar mindre om 3-SAT och mer om vem som hittade svaret: två AI-system omkullkastade oberoende en förmodan som mänskliga experter hade litat på i en generation.
AI som forskningskollega
Forskare beskriver nu hur nya AI-resultat landar varje eller varannan vecka och stör projekt som redan pågår. Formella verktyg som Lean blir centrala eftersom de låter människor lita på ett långt maskinskrivet bevis utan att härleda varje rad på nytt.
Dolda genvägar och självförbättring
ETH fångade en tro på att vissa sökproblem saknar smarta genvägar. Om den tron är fel kan andra uppenbart svåra problem också dölja genvägar.
Jag tänker på algoritmupptäckt som ett område där sådana genvägar kan spela stor roll för rekursiv självförbättring, idén om AI-system som hjälper till att designa bättre AI. Att använda AI för att hitta snabbare algoritmer är en konkret väg dit, även om inget i detta resultat gör det direkt idag.
Vad det betyder för datapratiker
För dig som bygger med data sticker tre lärdomar ut:
- Komplexitetsteori är inte bara akademisk: Att veta varför ett problem är NP-svårt talar om när du ska tänka på heuristiker, approximationer eller lösare i stället för exakt sökning.
- Verifiering är en färdighet: När AI genererar mer kod och analys är det minst lika viktigt att kontrollera utfallet (med tester, bevis eller reproducerbara pipelines) som att producera det.
- Asymptotik kan vilseleda: En ”snabbare” algoritm i teorin kan vara oanvändbar i verklig skala.
Slutsats
Om bevisen överlever expertgranskning hamnar den exponentiella tidshypotesen på den korta listan över allmänt trodda förmodanden som visade sig vara falska (som Eulers potatssummekonjektur). Men P kontra NP är fortfarande öppet och kryptografin är säker för tillfället.
Nästa milstolpar att hålla ögonen på är granskningsworkshopparna ledda av ETH:s ursprungliga författare, oberoende återimplementeringar av algoritmerna och om någon skärper gränsen ytterligare.
För att bygga grunderna bakom berättelser som denna, utforska våra kurser om datastrukturer och algoritmer, Python-programmering och maskininlärning. De täcker Big-O-tänkandet som gör resultat som detta läsbara.
OpenAI och Anthropic publicerade var sitt bevis på att den exponentiella tidshypotesen är falsk.
ETH är ett 27 år gammalt antagande inom teoretisk datavetenskap som säger att vissa problem aldrig kan lösas mycket snabbare än med brute force. Nu menar de ledande AI-labben att det helt enkelt inte stämmer.
Om bevisen håller är de de mest betydelsefulla AI-genererade resultaten i datavetenskap hittills. De tvingar också fram en omprövning av bokstavligen hundratals forskningsartiklar som utgick från att ETH var sann.
I den här artikeln förklarar vi vad den exponentiella tidshypotesen faktiskt betyder, tillsammans med P kontra NP, som är relaterat. Vi tittar också på exakt vad de två labben hävdar, hur bevisen kontrollerades och vad som (inte) förändras för kryptografi.
P kontra NP i klartext
P kontra NP frågar om varje problem vars svar är lätt att kontrollera också är lätt att lösa. Det är ett av de sju Millenniumprisen-problemen, och det är fortfarande olöst efter denna nyhet.
Sudoku är det klassiska exemplet. Att kontrollera ett ifyllt rutnät tar sekunder: skanna varje rad, kolumn och ruta efter upprepningar. Att hitta lösningen från ett i stort sett tomt rutnät kan ta mycket längre tid, och gapet exploderar när rutnätet växer.
Varje problem i P ligger också i NP. Den öppna frågan är om omvändningen gäller. De flesta datavetare tror att P ≠ NP, så att vissa problem i grunden är svårare att lösa än att kontrollera. Modern kryptografi lutar sig mot den tron: att kryptera är lätt, men att häva kryptering utan nyckel ska vara svårt.
Vad är den exponentiella tidshypotesen?
ETH är skarpare: den hävdar att ett specifikt NP-problem, 3-SAT, kräver exponentiell tid oavsett hur smart algoritmen är. Russell Impagliazzo och Ramamohan Paturi vid UC San Diego föreslog den i slutet av 1990-talet, med Francis Zane som bidrog till det grundläggande arbetet.
Problemet 3-SAT
I 3-SAT får du en formel bestående av n sann/falsk-variabler och en lista av klausuler. Varje klausul fogar samman tre villkor med ELLER, till exempel ”x₁ är sann ELLER x₄ är falsk ELLER x₇ är sann.” Uppgiften är att hitta en inställning av variablerna som uppfyller alla klausuler samtidigt.
Brute force testar alla 2ⁿ inställningar, så varje extra variabel fördubblar arbetet. Du ser hur det runt 100 variabler är hopplöst.
Vad ETH säger
ETH säger att det finns en konstant c > 1 sådan att ingen algoritm löser 3-SAT snabbare än cⁿ. Smartare algoritmer kan krympa basen under 2, men aldrig hela vägen ner till något subexponentiellt. Formellt: det existerar δ > 0 sådan att 3-SAT inte kan lösas på tid O(2δn).
Under decennier stämde framstegen med den bilden. Forskare fortsatte att hyvla ner basen, men den låg långt över 1. Eftersom 3-SAT kan konverteras till många andra problem blev ETH ett arbetshypotes. Forskare använde den för att hävda att problem som Clique, Vertex Cover, Independent Set och andra inte heller kan lösas mycket snabbare.
Hur det nya resultatet står sig
Den nya gränsen skrivs i kortform 2o(n). Kostnaden per tillagd variabel krymper mot 1 när n växer, vilket är precis vad ETH sa var omöjligt.
Vad OpenAI och Anthropic tillkännagav
Båda labben nådde i huvudsak samma subexponentiella gräns oberoende av varandra, och båda backade upp sina artiklar med maskinkontrollerade bevis i bevisassistenterna Lean.
Anthropic säger att Claude hittade kärnalgoritmen utan mänsklig input efter att ha producerat cirka 14 miljoner token i output. Metoden använder tensornätverk och rangargument. Forskare hjälpte sedan till med den slutliga artikeln.
Varför hittade båda labben den samma dag?
Inget av labben har förklarat tidpunkten. Anthropics artikel kallar de två resultaten oberoende och samtidiga, och de två texterna tar olika vägar genom matematiken för att nå i huvudsak samma gräns.
Viss kontext gör överlappet mindre förvånande än det först verkar. Båda labben har riktat sina modeller mot långa listor av olösta problem, och OpenAI ensam släppte hundratals AI-genererade matematikmanuskript i början av oktober. ETH är ett av de mest kända målen i fältet, och båda modellerna lärde sig från samma publicerade forskning. Oberoende, samtidiga upptäckter är också ett gammalt mönster i vetenskapen, som med Newton och Leibniz om kalkyl eller Darwin och Wallace om naturligt urval.
Hur solida är bevisen?
Lean bekräftar att ett formellt påstående följer logiskt från dess axiom. Det kan inte bekräfta att det formella påståendet säger samma sak som artikeln. Anthropic noterar att ingen maskin kontrollerar denna överensstämmelse, och OpenAI säger att deras Lean-fil bevisar en något svagare gräns än rubriken.
Nu organiserar samma forskare som föreslog problemet, Impagliazzo och Paturi, tillsammans med MIT:s Ryan Williams, workshops för att bedöma om de formella påståendena verkligen fångar ETH. Deras brev understryker att deltagande i granskningen inte är ett godkännande. Just nu, när denna artikel skrivs, har ingen offentligt hittat ett fel.
Williams har sagt att delar av OpenAIs bevis ser rutinmässiga ut, medan ”två eller tre utomjordiskt utseende delar” fortfarande behöver noggrann granskning. Impagliazzo, en av ETH:s författare, har beskrivit resultatet som djupt överraskande.
Vad som förändras och vad som inte gör det
I praktiken förändras nästan ingenting idag (puh): de nya algoritmerna slår bara brute force på indata som är långt större än vad en dator någonsin skulle kunna rymma.
Inga snabbare SAT-lösare
Anthropics artikel säger att metoden bara slår brute force på astronomiskt stora indata. För typiska formler med fem klausuler per variabel ligger brytpunkten vid ett tal med cirka 10 000 siffror. I det mest allmänna fallet är det ett tal med ungefär 100 miljoner siffror.
Författarna säger också att deras angreppssätt sannolikt inte hjälper på något under cirka 10 miljoner variabler. De SAT-lösare som används i kretsverifiering, schemaläggning och planering blir inte snabbare av detta resultat.
Kryptografi är inte krossad
Resultatet rör inte P kontra NP. Ingen låtsas det. OpenAI säger att de kontrollerade om algoritmen bryter verkliga kryptosystem och är ganska säkra på att den inte gör det.
Teorin skrivs om
Den större effekten gäller forskningen. Svårighetsresultat som bygger på ETH eller SETH behöver nu ny grund, och vissa forskare har sagt att år av deras eget arbete kan behöva ses över. Allt faller dock inte. Anthropic noterar att resultatet inte motbevisar problemet med ortogonala vektorer, som stöder många finkorniga komplexitetsresultat.
Varför det spelar roll för AI
Rubriken handlar mindre om 3-SAT och mer om vem som hittade svaret: två AI-system omkullkastade oberoende en förmodan som mänskliga experter hade litat på i en generation.
AI som forskningskollega
Forskare beskriver nu hur nya AI-resultat landar varje eller varannan vecka och stör projekt som redan pågår. Formella verktyg som Lean blir centrala eftersom de låter människor lita på ett långt maskinskrivet bevis utan att härleda varje rad på nytt.
Dolda genvägar och självförbättring
ETH fångade en tro på att vissa sökproblem saknar smarta genvägar. Om den tron är fel kan andra uppenbart svåra problem också dölja genvägar.
Jag tänker på algoritmupptäckt som ett område där sådana genvägar kan spela stor roll för rekursiv självförbättring, idén om AI-system som hjälper till att designa bättre AI. Att använda AI för att hitta snabbare algoritmer är en konkret väg dit, även om inget i detta resultat gör det direkt idag.
Vad det betyder för datapratiker
För dig som bygger med data sticker tre lärdomar ut:
Slutsats
Om bevisen överlever expertgranskning hamnar den exponentiella tidshypotesen på den korta listan över allmänt trodda förmodanden som visade sig vara falska (som Eulers potatssummekonjektur). Men P kontra NP är fortfarande öppet och kryptografin är säker för tillfället.
Nästa milstolpar att hålla ögonen på är granskningsworkshopparna ledda av ETH:s ursprungliga författare, oberoende återimplementeringar av algoritmerna och om någon skärper gränsen ytterligare.
För att bygga grunderna bakom berättelser som denna, utforska våra kurser om datastrukturer och algoritmer, Python-programmering och maskininlärning. De täcker Big-O-tänkandet som gör resultat som detta läsbara.