Eksponentialtidshypotesen (ETH)

Noen oppgaver kan vi bare løse ved å prøve nesten alle muligheter. Eksponentialtidshypotesen, på engelsk Exponential Time Hypothesis og forkortet ETH, er informatikernes veddemål om at det ikke går an å gjøre det på noen annen måte for én bestemt oppgave, uansett hvor smarte vi er. Raskere framgangsmåter finnes, men selv de beste vil trenge et antall skritt som vokser eksponentielt med oppgavens størrelse.

ETH henger tett sammen med problemet P versus NP, som vi har en egen artikkel om. Hvis du ikke har lest den, ta en titt der først, for vi bygger videre på den. Spesielt på hva kompleksiteten til en algoritme er, og hvorfor det er en slik avgrunn mellom n² og 2ⁿ.

Hvem skal du invitere til festen

Du planlegger en fest og vil invitere fire venner: Thomas, Jon, Kari og Daniel. Haken er at det er ulike forhold mellom dem, og du vil gjerne at alle blir fornøyde. Etter lang utspørring ender du opp med seks betingelser:

Thomas eller Kari kommer (gjerne begge).
Jon og Kari tåler ikke hverandre, så de kommer ikke begge to.
Daniel kommer bare hvis Jon også kommer.
Hvis Thomas kommer, må Kari eller Daniel også komme.
Hvis både Thomas og Kari kommer, må Jon også komme.
Minst én av trioen Thomas, Jon, Daniel kommer.

Hvem skal du invitere for at alle betingelsene skal gjelde samtidig? Prøv å finne det ut selv, løsningen sparer vi til slutten av artikkelen.

Informatikere ville skrevet om oppgaven til utsagnslogikkens språk. Hver venn får en bokstav, for eksempel T for Thomas. Bokstaven er enten sann (Thomas kommer) eller usann (Thomas kommer ikke). Symbolet ∨ leser vi «eller», og ¬ leser vi «ikke». Den første betingelsen ser da slik ut:

$T \lor K$

Den andre betingelsen sier at Jon ikke kommer, eller at Kari ikke kommer:

$\neg J \lor \neg K$

Ved den tredje betingelsen er det lett å tenke feil. «Daniel kommer bare hvis Jon også kommer» betyr at det ikke må skje at Daniel kommer og Jon ikke. Altså kommer enten Daniel ikke, eller Jon kommer:

$\neg D \lor J$

På samme måte skriver vi om resten. Hele oppgaven ser da slik ut:

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

Se hvor like betingelsene er: noen få bokstaver, noen med tegnet ¬, forbundet med ordet «eller». Og ingen av dem har mer enn tre bokstaver. En oppgave der vi har slike betingelser og skal tilordne bokstavene sann og usann slik at alle gjelder samtidig, kalles 3-SAT. Tallet tre betyr at en betingelse har høyst tre bokstaver, og SAT er en forkortelse av det engelske satisfiability, oppfyllbarhet.

Ved første blikk er det en lek til gåtesiden. Men en enorm mengde praktiske oppgaver kan skrives om til 3-SAT: timeplaner, kontroll av at en brikke i en prosessor regner riktig, vaktplanlegging og også sudoku. Da er det ikke fire bokstaver, men fort millioner.

Hvor mange muligheter må vi prøve?

Den mest direkte framgangsmåten er å prøve alt. Thomas kommer eller kommer ikke, det er to muligheter. For hver av dem kommer Jon eller kommer ikke, det er allerede fire muligheter. For fire venner er det

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

Slik resonnerte vi også ved de binære vektorene i artikkelen om P versus NP. Har vi n bokstaver, kan vi tilordne dem sann og usann på 2ⁿ måter. For 4 venner er det 16 muligheter, som du går gjennom på noen få minutter. For 100 bokstaver er det

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

muligheter. Hvis en datamaskin prøvde en milliard muligheter i sekundet, ville den trengt omtrent tre tusen ganger så lang tid som universet har eksistert.

Omvendt er det derimot lett: Hvis noen sier til deg «inviter disse tre», kontrollerer du det med en gang. Det holder å gå gjennom de seks betingelsene og for hver av dem se etter om den gjelder. Å finne en løsning er vanskelig, å kontrollere den er lett. Akkurat slike oppgaver plasserte vi i artikkelen om P versus NP i klassen NP.

Men 3-SAT er ikke en hvilken som helst oppgave i NP: I 1971 ble det vist at hver eneste oppgave i NP kan oversettes til 3-SAT. Den som kunne løse 3-SAT raskt, ville altså raskt kunne løse alt som kan kontrolleres raskt. Oppgaver med den egenskapen kalles NP-komplette, og 3-SAT er den mest kjente representanten for dem.

Går det raskere enn 2ⁿ?

Ja. Det er unødvendig å prøve absolutt alt. Det holder for eksempel å legge merke til at Thomas ikke kommer: Av den første betingelsen følger det da straks at Kari må komme. Alle mulighetene der ingen av dem kommer, stryker vi med en gang. Smarte algoritmer kombinerer en hel rekke slike triks. De beste vi kjenner i dag trenger omtrent

${1,307}^{n}$

skritt. Det er et enormt sprang. For n = 100 blir det i stedet for 10³⁰ omtrent 4,2 · 10¹¹ skritt, noe en datamaskin klarer på noen få minutter.

Men pass på, det er en hake. 1,307ⁿ er fortsatt en eksponentialfunksjon. Vi har gjort grunntallet mindre, fra to til 1,307, men variabelen n står fortsatt i eksponenten. Når n fortsetter å vokse, kjører det over oss til slutt likevel. For n = 1000 er selv 1,307ⁿ et tall med 117 sifre.

Og hvordan ville en algoritme se ut som ikke er eksponentiell? For eksempel en som klarer seg med n³ skritt. Den ville vært polynomisk, og 3-SAT ville da hørt til klassen P. Mellom polynomer og eksponentialfunksjoner finnes det likevel en gråsone: funksjoner som vokser raskere enn hvert polynom og likevel langsommere enn hver eksponentialfunksjon. For eksempel

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

Her står det bare kvadratroten av n i eksponenten. La oss sammenligne alle fire funksjonene i en tabell:

n	n³	$2^{\sqrt{n}}$	1,307ⁿ	2ⁿ
20	8000	22	212	1 048 576
100	10⁶	1024	4,2 · 10¹¹	1,3 · 10³⁰
1000	10⁹	3,3 · 10⁹	1,9 · 10¹¹⁶	1,1 · 10³⁰¹

For n = 1000 spiller $2^{\sqrt{n}}$ i samme liga som n³, mens begge eksponentialfunksjonene har stukket av til tall vi ikke engang har navn på. Funksjoner som $2^{\sqrt{n}}$ , som vokser langsommere enn cⁿ for ethvert grunntall c større enn én, kalles subeksponentielle.

Det samme viser grafen. Den loddrette aksen er logaritmisk: Hver strek oppover betyr et hundre tusen ganger større tall. Ellers ville ingenting bortsett fra 2ⁿ fått plass i figuren.

$Vekst for funksjonene 2^n (rød), 1{,}307^n (oransje), 2^{\sqrt{n}} (blå) og n^3 (grønn) med logaritmisk loddrett akse$

Eksponentialfunksjoner er i en slik graf rette linjer som hele tiden stiger. Den røde 2ⁿ er brattere enn den oransje 1,307ⁿ, men begge er rette linjer. Det interessante er at den oransje i begynnelsen til og med ligger under den grønne n³. Den går forbi den først rundt n = 42, men da for godt. Den blå $2^{\sqrt{n}}$ bøyer derimot av og holder seg nede ved den grønne.

Hva ETH nøyaktig hevder

Nå kan vi uttale hypotesen. I 1999 ble den formulert av Russell Impagliazzo og Ramamohan Paturi:

Det finnes et tall c større enn én slik at ingen algoritme kan løse 3-SAT med n bokstaver raskere enn på omtrent cⁿ skritt.

Og på vanlig norsk? Eksponentialfunksjonens grunntall kan vi gjøre mindre med smarte triks, fra to til 1,5, til 1,307, kanskje en dag til 1,2. Men vi presser det aldri vilkårlig nær én. Et sted er det en grense som det ikke går under. En algoritme med kompleksitet $2^{\sqrt{n}}$ burde altså ifølge ETH ikke finnes.

Hvorfor hypotese? Fordi ingen kan bevise den. ETH er en arbeidsantakelse, omtrent som vi i artikkelen om P versus NP antar at P ≠ NP. De fleste informatikere tror på den, fordi tiår med anstrengelser bare har ført til at grunntallet sakte kryper nedover fra to. Noe bevis har likevel ingen i hånden.

ETH og P versus NP

Hvordan henger disse to spørsmålene sammen? Tenk deg at 3-SAT har en «sann» vanskelighetsgrad, den raskest mulige algoritmen. Den kan ligge i tre soner:

Tre vanskelighetssoner for 3-SAT: polynomisk (grønn), subeksponentiell (blå) og eksponentiell (rød)

Grønn sone, polynomisk. 3-SAT kan løses for eksempel på n³ skritt. Siden 3-SAT er NP-komplett, ville da P = NP gjelde, og ETH ville selvfølgelig ikke gjelde.
Blå sone, subeksponentiell. 3-SAT kan løses på $2^{\sqrt{n}}$ skritt eller noe lignende. Polynomisk går det ikke, så P ≠ NP gjelder. Men ETH ville ikke gjelde.
Rød sone, eksponentiell. Bedre enn cⁿ går det ikke. ETH gjelder, og dermed gjelder også P ≠ NP.

Av figuren ser vi at ETH er en sterkere påstand enn P ≠ NP. Den sier ikke bare at 3-SAT ikke kan løses polynomisk, men at det heller ikke kan løses subeksponentielt. Den som beviste ETH, ville dermed også bevise P ≠ NP og få en million dollar.

Og omvendt: Den som motbeviste ETH, har dermed ikke nødvendigvis bevist P = NP. Det holder med en algoritme fra den blå sonen. Husk det, vi bruker det om litt.

Hva er ETH god for

Å bevise at en oppgave ikke kan løses raskt, er utrolig vanskelig i informatikk. Nesten ingenting av den typen kan vi. ETH gir oss en bakdør: I stedet for «oppgave X er vanskelig» beviser vi «oppgave X er vanskelig, hvis ETH gjelder».

Hvordan? Vi viser at hvis oppgave X kunne løses raskt, ville også 3-SAT kunne løses raskt. Ta for eksempel denne: Vi har n personer, og om noen par vet vi at de ikke tåler hverandre. Vi vil fordele dem på tre rom slik at ikke noe slikt par havner i samme rom. Informatikere kaller det å farge en graf med tre farger. Ut fra hver 3-SAT-oppgave kan den konstrueres slik at antallet personer bare blir et multiplum av antallet bokstaver. Hvis personene altså kunne fordeles på rommene subeksponentielt, kunne også 3-SAT løses subeksponentielt, og ETH ville falle.

Slike betingede resultater finnes det i dag hundrevis av. Hele fagfeltet som undersøker hvor vanskelige enkeltoppgaver nøyaktig er, står på ETH som et hus på sitt fundament.

ETH har også en sterkere søster, den sterke eksponentialtidshypotesen (SETH). Den retter seg mot oppgaver der betingelsene kan ha flere enn tre bokstaver, for eksempel ti eller hundre. SETH hevder at jo lengre betingelser vi tillater, desto nærmere to kommer det best mulige grunntallet. For lange betingelser kunne man altså nesten ikke spare noe i forhold til den dumme utprøvingen av alle 2ⁿ mulighetene.

Hvorfor det snakkes om ETH nå

Selskapet OpenAI, som du kjenner først og fremst fra ChatGPT, offentliggjorde i oktober 2026 en preprint, altså en artikkel som ennå ikke er fagfellevurdert. Den heter The Exponential Time Hypothesis is False, på norsk «Eksponentialtidshypotesen er falsk». I den hevder selskapet å ha funnet en algoritme som løser 3-SAT på omtrent

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

skritt. I eksponenten står det altså ikke bare n, men n delt på kvadratroten av den (naturlige) logaritmen. Den nevneren vokser fryktelig langsomt, men den vokser, og det holder for at funksjonen skal være subeksponentiell. Algoritmen skal til og med ikke bare kunne finne én løsning, men også telle hvor mange løsninger det finnes.

Hvis det stemte, ville algoritmen fra OpenAI havne i den blå sonen i figuren ovenfor. Og hva ville det bety?

ETH ville falle, og med den også SETH og hundrevis av betingede resultater som bygde på dem. Informatikerne ville måtte kaste eller skrive om mange «hvis ETH gjelder, så …».
Problemet P versus NP ville det ikke løse. Algoritmen er fortsatt ikke polynomisk.
I praksis ville nesten ingenting endre seg. I formelen skjuler det seg konstanter som vi ikke kjenner. Hvis de var lik én, ville $\sqrt{\ln n}$ for n = 1000 bli omtrent 2,6, og vi ville fått omtrent 2³⁸⁰ skritt. Det er nesten det samme som 1,307¹⁰⁰⁰ ≈ 2³⁸⁶ ved dagens beste algoritmer. Den nye ville først gå tydelig forbi dagens algoritmer for enda større n, og med hvor mye avhenger nettopp av de ukjente konstantene. Den har altså først og fremst teoretisk betydning. Kryptering og bankvesen berøres ikke.

Foreløpig er det en ubekreftet påstand. Beviset er langt og teknisk, og ekspertene har akkurat begynt å lese det. Store kunngjøringer om løste problemer har mange ganger tidligere vist seg å være feilaktige, så inntil videre gjelder: Vi venter og ser hva ekspertene sier til det. Dette avsnittet skriver vi 27. oktober 2026.

Løsning på oppgaven med festen

Du skal invitere Thomas, Jon og Daniel, ikke Kari. Figuren viser alle 16 mulighetene. I hver kolonne er det én mulighet: En fylt sirkel betyr at vennen kommer, en tom at han ikke kommer. Det røde tallet under kolonnen viser den første betingelsen som ikke gjelder. Den eneste muligheten der alle betingelsene gjelder, er innrammet med grønt.

Alle 16 mulighetene for hvem man kan invitere. Radene svarer til vennene T, J, K, D, en fylt sirkel betyr at vedkommende kommer.

Og nettopp dette er den rå makten som ETH regner som nesten uslåelig: for fire venner seksten kolonner, for hundre venner flere kolonner enn det er atomer i kroppen vår.

Se også

« Forrige: Det største problemet i informatikk: P versus NP

Neste: Trachtenbergs metode for rask addisjon »