Exponentialtidshypotesen (ETH)

Vissa uppgifter kan vi bara lösa genom att pröva nästan alla möjligheter. Exponentialtidshypotesen, på engelska Exponential Time Hypothesis och förkortad ETH, är datavetarnas vad om att det inte går att göra på något annat sätt för en alldeles bestämd uppgift, hur listiga vi än är. Snabbare metoder finns, men även de bästa kommer att behöva ett antal steg som växer exponentiellt med uppgiftens storlek.

ETH hänger nära ihop med problemet P mot NP, som vi har en egen artikel om. Om du inte har läst den, kika in där först, för vi bygger vidare på den. Framför allt på vad en algoritms komplexitet är och varför det är en sådan avgrund mellan n² och 2ⁿ.

Vem ska du bjuda till festen

Du planerar en fest och vill bjuda fyra kompisar: Tobias, Johan, Karin och David. Haken är att det råder olika förhållanden mellan dem och att du gärna vill att alla ska bli nöjda. Efter långt utfrågande kommer du fram till sex villkor:

1. Tobias eller Karin kommer (gärna båda).
2. Johan och Karin tål inte varandra, så de kommer inte båda två.
3. David kommer bara om Johan också kommer.
4. Om Tobias kommer måste Karin eller David också komma.
5. Om både Tobias och Karin kommer måste Johan också komma.
6. Minst en av trion Tobias, Johan, David kommer.

Vem ska du bjuda för att alla villkor ska gälla samtidigt? Försök komma på det själv, lösningen sparar vi till slutet av artikeln.

Datavetare skulle skriva om uppgiften till satslogikens språk. Varje kompis får en bokstav, till exempel T för Tobias. Bokstaven är antingen sann (Tobias kommer) eller falsk (Tobias kommer inte). Symbolen ∨ läser vi ”eller” och ¬ läser vi ”inte”. Det första villkoret ser då ut så här:

$$T\vee K$$

Det andra villkoret säger att Johan inte kommer eller att Karin inte kommer:

$$\mathrm{\neg }J\vee \mathrm{\neg }K$$

Vid det tredje villkoret är det lätt att tänka fel. ”David kommer bara om Johan också kommer” betyder att det inte får hända att David kommer och Johan inte. Alltså kommer antingen David inte, eller så kommer Johan:

$$\mathrm{\neg }D\vee J$$

På samma sätt skriver vi om resten. Hela uppgiften ser då ut så här:

$$\begin{array}{rcl}1.& & T\vee K\\ 2.& & \mathrm{\neg }J\vee \mathrm{\neg }K\\ 3.& & \mathrm{\neg }D\vee J\\ 4.& & \mathrm{\neg }T\vee K\vee D\\ 5.& & \mathrm{\neg }T\vee \mathrm{\neg }K\vee J\\ 6.& & T\vee J\vee D\end{array}$$

Titta på hur lika villkoren är: några bokstäver, en del med tecknet ¬, förbundna med ordet ”eller”. Och inget av dem har fler än tre bokstäver. En uppgift där vi har sådana villkor och ska tilldela bokstäverna sant och falskt så att alla gäller samtidigt kallas 3-SAT. Trean betyder att ett villkor har högst tre bokstäver, och SAT är en förkortning av engelskans satisfiability, satisfierbarhet.

Vid första anblick är det en lek för pysselhörnan. Men en enorm mängd praktiska uppgifter går att skriva om till formen 3-SAT: scheman, kontroll av att ett chip i en processor räknar rätt, planering av arbetspass och även sudoku. Då är det inte fyra bokstäver, utan lätt miljontals.

Hur många möjligheter måste prövas?

Det mest rättframma sättet är att pröva allt. Tobias kommer eller kommer inte, det är två möjligheter. För var och en av dem kommer Johan eller kommer inte, det är redan fyra möjligheter. För fyra kompisar blir det

$$2\cdot 2\cdot 2\cdot 2=2^4=16.$$

Likadant resonerade vi vid de binära vektorerna i artikeln om P mot NP. Har vi n bokstäver kan vi tilldela dem sant och falskt på 2ⁿ sätt. För 4 kompisar är det 16 möjligheter, som du går igenom på några minuter. För 100 bokstäver är det

$$2^{100}\approx 1,27\cdot {10}^{30}$$

möjligheter. Om en dator prövade en miljard möjligheter per sekund skulle den behöva ungefär tretusen gånger så lång tid som universum har funnits.

Åt andra hållet är det däremot lätt: Om någon säger ”bjud de här tre” kontrollerar du det direkt. Det räcker att gå igenom de sex villkoren och för vart och ett se efter om det gäller. Att hitta en lösning är svårt, att kontrollera den är lätt. Precis sådana uppgifter placerade vi i artikeln om P mot NP i klassen NP.

Men 3-SAT är ingen vilken uppgift som helst i NP: År 1971 visades att varje uppgift i NP kan översättas till 3-SAT. Den som snabbt kunde lösa 3-SAT skulle alltså snabbt kunna lösa allt som går att kontrollera snabbt. Uppgifter med den egenskapen kallas NP-fullständiga, och 3-SAT är deras mest kända representant.

Går det snabbare än 2ⁿ?

Ja. Det är onödigt att pröva absolut allt. Det räcker till exempel att lägga märke till att Tobias inte kommer: Ur det första villkoret följer då direkt att Karin måste komma. Alla möjligheter där ingen av dem kommer stryker vi på en gång. Listiga algoritmer kombinerar en hel rad sådana knep. De bästa vi känner till i dag behöver ungefär

$${\mathrm{1,307}}^n$$

steg. Det är ett enormt språng. För n = 100 blir det i stället för 10³⁰ ungefär 4,2 · 10¹¹ steg, vilket en dator klarar på några minuter.

Men se upp, här finns en fälla. 1,307ⁿ är fortfarande en exponentialfunktion. Vi har minskat basen från två till 1,307, men variabeln n står kvar i exponenten. När n fortsätter att växa kör det över oss till sist ändå. För n = 1000 är även 1,307ⁿ ett tal med 117 siffror.

Och hur skulle en algoritm se ut som inte är exponentiell? Till exempel en som klarar sig med n³ steg. Den skulle vara polynomiell, och 3-SAT skulle då tillhöra klassen P. Mellan polynom och exponentialfunktioner finns det dock en gråzon: funktioner som växer snabbare än varje polynom och ändå långsammare än varje exponentialfunktion. Till exempel

$$2^{\sqrt{n}}.$$

Här står bara roten ur n i exponenten. Låt oss jämföra alla fyra funktionerna i en tabell:

För n = 1000 spelar $2^{\sqrt{n}}$ i samma liga som n³, medan båda exponentialfunktionerna har rymt iväg till tal som vi inte ens har namn på. Funktioner som $2^{\sqrt{n}}$, vilka växer långsammare än cⁿ för vilken bas c som helst större än ett, kallas subexponentiella.

Samma sak visar grafen. Den lodräta axeln är logaritmisk: Varje streck uppåt betyder ett hundratusen gånger större tal. Annars skulle ingenting utom 2ⁿ rymmas i bilden.

Exponentialfunktioner är i en sådan graf räta linjer som hela tiden stiger. Den röda 2ⁿ är brantare än den orangea 1,307ⁿ, men båda är räta linjer. Intressant är att den orangea i början till och med ligger under den gröna n³. Den går förbi den först vid ungefär n = 42, men då för gott. Den blå $2^{\sqrt{n}}$ böjer sig däremot av och håller sig nere vid den gröna.

Vad ETH exakt påstår

Nu kan vi uttala hypotesen. År 1999 formulerades den av Russell Impagliazzo och Ramamohan Paturi:

Det finns ett tal c större än ett sådant att ingen algoritm kan lösa 3-SAT med n bokstäver snabbare än på ungefär cⁿ steg.

Och på vanlig svenska? Exponentialfunktionens bas kan vi minska med listiga knep, från två till 1,5, till 1,307, kanske en dag till 1,2. Men vi pressar den aldrig godtyckligt nära ett. Någonstans finns det en gräns som det inte går under. En algoritm med komplexiteten $2^{\sqrt{n}}$ borde alltså enligt ETH inte finnas.

Varför hypotes? För att ingen kan bevisa den. ETH är ett arbetsantagande, ungefär som vi i artikeln om P mot NP antar att P ≠ NP. De flesta datavetare tror på den, eftersom årtionden av ansträngningar bara har lett till att basen sakta kryper nedåt från två. Något bevis har dock ingen i handen.

ETH och P mot NP

Hur hänger de här två frågorna ihop? Föreställ dig att 3-SAT har en ”sann” svårighetsgrad, den snabbast möjliga algoritmen. Den kan ligga i tre zoner:

• Grön zon, polynomiell. 3-SAT går att lösa till exempel på n³ steg. Eftersom 3-SAT är NP-fullständigt skulle då P = NP gälla, och ETH skulle naturligtvis inte gälla.
• Blå zon, subexponentiell. 3-SAT går att lösa på $2^{\sqrt{n}}$ steg eller något liknande. Polynomiellt går det inte, så P ≠ NP gäller. Men ETH skulle inte gälla.
• Röd zon, exponentiell. Bättre än cⁿ går det inte. ETH gäller, och därmed gäller även P ≠ NP.

Av bilden syns det att ETH är ett starkare påstående än P ≠ NP. Den säger inte bara att 3-SAT inte går att lösa polynomiellt, utan att det inte heller går att lösa subexponentiellt. Den som bevisade ETH skulle därmed också bevisa P ≠ NP och få en miljon dollar.

Och tvärtom: Den som motbevisade ETH har därmed inte nödvändigtvis bevisat P = NP. Det räcker med en algoritm från den blå zonen. Kom ihåg det, vi utnyttjar det om en stund.

Vad är ETH bra för

Att bevisa att en uppgift inte går att lösa snabbt är otroligt svårt inom datavetenskapen. Nästan inget sådant kan vi. ETH ger oss en bakdörr: I stället för ”uppgift X är svår” bevisar vi ”uppgift X är svår, om ETH gäller”.

Hur? Vi visar att om uppgift X gick att lösa snabbt, skulle även 3-SAT gå att lösa snabbt. Ta till exempel den här: Vi har n personer, och om vissa par vet vi att de inte tål varandra. Vi vill fördela dem på tre rum så att inget sådant par hamnar i samma rum. Datavetare kallar det att färga en graf med tre färger. Ur varje uppgift av typen 3-SAT går den att konstruera så att antalet personer bara blir en multipel av antalet bokstäver. Om personerna alltså gick att fördela på rummen subexponentiellt, skulle även 3-SAT gå att lösa subexponentiellt och ETH skulle falla.

Sådana villkorliga resultat finns det i dag hundratals av. Hela det område som undersöker hur svåra enskilda uppgifter exakt är står på ETH som ett hus på sin grund.

ETH har också en starkare syster, den starka exponentialtidshypotesen (SETH). Den inriktar sig på uppgifter där villkoren får ha fler än tre bokstäver, till exempel tio eller hundra. SETH påstår att ju längre villkor vi tillåter, desto närmare två kommer den bästa möjliga basen. För långa villkor skulle man alltså knappt kunna spara något jämfört med det dumma prövandet av alla 2ⁿ möjligheter.

Varför det pratas om ETH just nu

Företaget OpenAI, som du känner framför allt genom ChatGPT, publicerade i oktober 2026 en preprint, alltså en artikel som ännu inte har granskats av andra forskare. Den heter The Exponential Time Hypothesis is False, på svenska ”Exponentialtidshypotesen är falsk”. I den påstår företaget sig ha hittat en algoritm som löser 3-SAT på ungefär

$$2^{\frac{n}{\sqrt{\ln n}}}$$

steg. I exponenten står det alltså inte bara n, utan n delat med roten ur den (naturliga) logaritmen. Den nämnaren växer förfärligt långsamt, men den växer, och det räcker för att funktionen ska vara subexponentiell. Algoritmen ska till och med inte bara kunna hitta en lösning, utan även räkna hur många lösningar det finns.

Om det stämde skulle algoritmen från OpenAI hamna i den blå zonen i bilden ovan. Och vad skulle det betyda?

• ETH skulle falla och med den även SETH och hundratals villkorliga resultat som vilade på dem. Datavetare skulle få kasta bort eller skriva om många ”om ETH gäller, då …”.
• Problemet P mot NP skulle det inte lösa. Algoritmen är fortfarande inte polynomiell.
• I praktiken skulle nästan ingenting förändras. I formeln gömmer sig konstanter som vi inte känner till. Om de var lika med ett skulle $\sqrt{\ln n}$ för n = 1000 bli ungefär 2,6 och vi skulle få ungefär 2³⁸⁰ steg. Det är nästan detsamma som 1,307¹⁰⁰⁰ ≈ 2³⁸⁶ hos dagens bästa algoritmer. Den nya skulle gå tydligt förbi dagens algoritmer först för ännu större n, och med hur mycket beror just på de okända konstanterna. Den har alltså framför allt teoretisk betydelse. Kryptering och bankväsen berörs inte.

Hittills är det ett ogranskat påstående. Beviset är långt och tekniskt, och experterna har först nu börjat läsa det. Stora tillkännagivanden om lösta problem har många gånger visat sig vara felaktiga, så tills vidare gäller: Vi väntar och ser vad experterna säger om det. Det här stycket skriver vi den 27 oktober 2026.

Lösning på uppgiften med festen

Du ska bjuda Tobias, Johan och David, inte Karin. Bilden visar alla 16 möjligheter. I varje kolumn finns en möjlighet: En fylld cirkel betyder att kompisen kommer, en tom att han inte kommer. Det röda talet under kolumnen visar det första villkoret som inte gäller. Den enda möjligheten där alla villkor gäller är inramad i grönt.

Och just det här är det råa våld som ETH anser vara nästan oöverträffbart: för fyra kompisar sexton kolumner, för hundra kompisar fler kolumner än det finns atomer i vår kropp.

Se även

• Datavetenskapens största problem: P mot NP
• Satslogik
• Exponentialfunktion
• Exponentiell tillväxt