Eksponentialtidshypotesen (ETH)

Nogle opgaver kan vi kun løse ved at prøve næsten alle muligheder. Eksponentialtidshypotesen, på engelsk Exponential Time Hypothesis og forkortet ETH, er datalogers væddemål om, at det ikke kan gøres anderledes ved én bestemt opgave, uanset hvor kloge vi er. Hurtigere fremgangsmåder findes, men selv de bedste vil have brug for et antal skridt, der vokser eksponentielt med opgavens størrelse.

ETH hænger tæt sammen med problemet P versus NP, som vi har en selvstændig artikel om. Hvis du ikke har læst den, så kig ind der først, for vi bygger videre på den. Især på, hvad en algoritmes kompleksitet er, og hvorfor der er sådan en afgrund mellem n² og 2ⁿ.

Hvem skal du invitere til festen

Du planlægger en fest og vil invitere fire venner: Thomas, Jens, Karen og Dennis. Problemet er, at der er forskellige forhold mellem dem, og du vil gerne have, at alle bliver tilfredse. Efter lang tids rundspørge ender du med seks betingelser:

1. Thomas eller Karen kommer (gerne begge).
2. Jens og Karen kan ikke fordrage hinanden, så de kommer ikke begge to.
3. Dennis kommer kun, hvis Jens også kommer.
4. Hvis Thomas kommer, skal Karen eller Dennis også komme.
5. Hvis både Thomas og Karen kommer, skal Jens også komme.
6. Mindst én af trioen Thomas, Jens, Dennis kommer.

Hvem skal du invitere, for at alle betingelser gælder på én gang? Prøv selv at finde ud af det, løsningen gemmer vi til slutningen af artiklen.

Dataloger ville omskrive opgaven til udsagnslogikkens sprog. Hver ven får et bogstav, for eksempel T for Thomas. Bogstavet er enten sandt (Thomas kommer) eller falsk (Thomas kommer ikke). Symbolet ∨ læser vi »eller«, og ¬ læser vi »ikke«. Den første betingelse ser så sådan ud:

$$T\vee K$$

Den anden betingelse siger, at Jens ikke kommer, eller Karen ikke kommer:

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

Ved den tredje betingelse er det let at komme galt af sted. »Dennis kommer kun, hvis Jens også kommer« betyder, at det ikke må ske, at Dennis kommer og Jens ikke. Altså kommer enten Dennis ikke, eller også kommer Jens:

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

På samme måde omskriver vi resten. Hele opgaven ser så sådan ud:

$$\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}$$

Se, hvor ens betingelserne er: nogle få bogstaver, nogle med tegnet ¬, forbundet med ordet »eller«. Og ingen af dem har mere end tre bogstaver. En opgave, hvor vi har sådanne betingelser og skal tildele bogstaverne sandt og falsk, så alle gælder på én gang, hedder 3-SAT. Tallet tre betyder, at en betingelse har højst tre bogstaver, og SAT er en forkortelse af det engelske satisfiability, opfyldelighed.

Ved første øjekast er det en leg til puslespilssiden. Men et enormt antal praktiske opgaver kan omskrives til 3-SAT: skemaer, kontrol af, at en chip i en processor regner rigtigt, vagtplanlægning og også sudoku. Så er der ikke fire bogstaver, men sagtens millioner.

Hvor mange muligheder skal vi prøve?

Den mest ligefremme fremgangsmåde er at prøve det hele. Thomas kommer, eller han kommer ikke, det er to muligheder. For hver af dem kommer Jens, eller han kommer ikke, det er allerede fire muligheder. For fire venner er der

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

Sådan ræsonnerede vi også ved de binære vektorer i artiklen om P versus NP. Har vi n bogstaver, kan vi tildele dem sandt og falsk på 2ⁿ måder. For 4 venner er det 16 muligheder, som du gennemgår på få minutter. For 100 bogstaver er det

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

muligheder. Hvis en computer prøvede en milliard muligheder i sekundet, ville den bruge omkring tre tusind gange så lang tid, som universet har eksisteret.

Omvendt er det dog let: Hvis nogen siger til dig »invitér de her tre«, kan du med det samme kontrollere det. Du skal bare gennemgå de seks betingelser og for hver af dem se efter, om den gælder. At finde en løsning er svært, at kontrollere den er let. Netop sådanne opgaver placerede vi i artiklen om P versus NP i klassen NP.

Men 3-SAT er ikke en hvilken som helst opgave i NP: I 1971 blev det vist, at enhver opgave i NP kan oversættes til 3-SAT. Den, der kunne løse 3-SAT hurtigt, ville altså hurtigt kunne løse alt, hvad der kan kontrolleres hurtigt. Opgaver med den egenskab hedder NP-fuldstændige, og 3-SAT er deres mest berømte repræsentant.

Kan det gå hurtigere end 2ⁿ?

Ja. Det er unødvendigt at prøve absolut alt. Det er for eksempel nok at bemærke, at Thomas ikke kommer: Af den første betingelse følger så straks, at Karen må komme. Alle muligheder, hvor ingen af dem kommer, stryger vi med det samme. Kloge algoritmer kombinerer en hel række af den slags tricks. De bedste, vi kender i dag, har brug for omkring

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

skridt. Det er et enormt spring. For n = 100 giver det i stedet for 10³⁰ omkring 4,2 · 10¹¹ skridt, og det klarer en computer på få minutter.

Men pas på, der er en hage. 1,307ⁿ er stadig en eksponentialfunktion. Vi har formindsket grundtallet fra to til 1,307, men variablen n står stadig i eksponenten. Når n fortsætter med at vokse, løber det os alligevel til sidst over ende. For n = 1000 er selv 1,307ⁿ et tal med 117 cifre.

Og hvordan ville en algoritme se ud, som ikke er eksponentiel? For eksempel en, der klarer sig med n³ skridt. Den ville være polynomiel, og 3-SAT ville så høre til klassen P. Mellem polynomier og eksponentialfunktioner ligger der dog en gråzone: funktioner, der vokser hurtigere end ethvert polynomium og alligevel langsommere end enhver eksponentialfunktion. For eksempel

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

Her står der kun kvadratroden af n i eksponenten. Lad os sammenligne alle fire funktioner i en tabel:

For n = 1000 spiller $2^{\sqrt{n}}$ i samme liga som n³, mens begge eksponentialfunktioner er løbet af sted til tal, vi ikke engang har navne til. Funktioner som $2^{\sqrt{n}}$, der vokser langsommere end cⁿ for ethvert grundtal c større end én, kaldes subeksponentielle.

Det samme viser grafen. Den lodrette akse er logaritmisk: Hver streg opad betyder et hundrede tusind gange større tal. Ellers ville der ikke være plads til andet end 2ⁿ i figuren.

Eksponentialfunktioner er i sådan en graf rette linjer, der hele tiden stiger. Den røde 2ⁿ er stejlere end den orange 1,307ⁿ, men begge er rette linjer. Det interessante er, at den orange i begyndelsen endda ligger under den grønne n³. Den overhaler den først omkring n = 42, men så til gengæld for altid. Den blå $2^{\sqrt{n}}$ bøjer derimod af og holder sig nede ved den grønne.

Hvad ETH præcist påstår

Nu kan vi udtale hypotesen. I 1999 formulerede Russell Impagliazzo og Ramamohan Paturi den:

Der findes et tal c større end én, så ingen algoritme kan løse 3-SAT med n bogstaver hurtigere end på omkring cⁿ skridt.

Og på almindeligt dansk? Eksponentialfunktionens grundtal kan vi formindske med kloge tricks, fra to til 1,5, til 1,307, måske en dag til 1,2. Men vi presser det aldrig vilkårligt tæt på én. Et sted er der en grænse, som det ikke kan komme under. En algoritme med kompleksiteten $2^{\sqrt{n}}$ burde derfor ifølge ETH ikke findes.

Hvorfor hypotese? Fordi ingen kan bevise den. ETH er en arbejdsantagelse, ligesom vi i artiklen om P versus NP antager, at P ≠ NP. De fleste dataloger tror på den, fordi årtiers bestræbelser kun har ført til, at grundtallet langsomt kryber nedad fra to. Et bevis har ingen dog i hånden.

ETH og P versus NP

Hvordan hænger de to spørgsmål sammen? Forestil dig, at 3-SAT har en »sand« sværhedsgrad, nemlig den hurtigst mulige algoritme. Den kan ligge i tre områder:

• Grønt område, polynomielt. 3-SAT kan løses for eksempel på n³ skridt. Da 3-SAT er NP-fuldstændigt, ville der så gælde P = NP, og ETH ville selvfølgelig ikke gælde.
• Blåt område, subeksponentielt. 3-SAT kan løses på $2^{\sqrt{n}}$ skridt eller noget lignende. Polynomielt ikke, så der gælder P ≠ NP. Men ETH ville ikke gælde.
• Rødt område, eksponentielt. Bedre end cⁿ kan det ikke gøres. ETH gælder, og dermed gælder også P ≠ NP.

Af figuren kan man se, at ETH er en stærkere påstand end P ≠ NP. Den siger ikke kun, at 3-SAT ikke kan løses polynomielt, men at det heller ikke kan løses subeksponentielt. Den, der beviste ETH, ville dermed også bevise P ≠ NP og få en million dollars.

Og omvendt: Den, der modbeviste ETH, har dermed ikke nødvendigvis bevist P = NP. Det er nok med en algoritme fra det blå område. Husk det, vi bruger det om lidt.

Hvad er ETH god til

At bevise, at en opgave ikke kan løses hurtigt, er utroligt svært i datalogi. Næsten ingenting af den slags kan vi. ETH giver os en bagdør: I stedet for »opgave X er svær« beviser vi »opgave X er svær, hvis ETH gælder«.

Hvordan? Vi viser, at hvis opgave X kunne løses hurtigt, ville 3-SAT også kunne løses hurtigt. Tag for eksempel denne: Vi har n personer, og om nogle par ved vi, at de ikke kan fordrage hinanden. Vi vil fordele dem på tre rum, så intet sådant par havner i samme rum. Dataloger kalder det at farve en graf med tre farver. Ud fra enhver 3-SAT-opgave kan den konstrueres, så antallet af personer kun bliver et multiplum af antallet af bogstaver. Hvis personerne kunne fordeles på rummene subeksponentielt, kunne 3-SAT altså også løses subeksponentielt, og ETH ville falde.

Af sådanne betingede resultater findes der i dag hundredvis. Hele det område, der undersøger, hvor svære de enkelte opgaver præcist er, står på ETH som et hus på sit fundament.

ETH har også en stærkere søster, den stærke eksponentialtidshypotese (SETH). Den retter sig mod opgaver, hvor betingelserne må have mere end tre bogstaver, for eksempel ti eller hundrede. SETH påstår, at jo længere betingelser vi tillader, desto tættere kommer det bedst mulige grundtal på to. For lange betingelser kunne man altså næsten intet spare i forhold til den dumme afprøvning af alle 2ⁿ muligheder.

Hvorfor der nu tales om ETH

Virksomheden OpenAI, som du især kender fra ChatGPT, offentliggjorde i oktober 2026 en preprint, altså en artikel, der endnu ikke er blevet fagfællebedømt. Den hedder The Exponential Time Hypothesis is False, på dansk »Eksponentialtidshypotesen er falsk«. I den påstår virksomheden at have fundet en algoritme, der løser 3-SAT på omkring

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

skridt. I eksponenten står der altså ikke bare n, men n divideret med kvadratroden af den (naturlige) logaritme. Den nævner vokser frygtelig langsomt, men den vokser, og det er nok til, at funktionen er subeksponentiel. Algoritmen skulle endda ikke kun kunne finde én løsning, men også tælle, hvor mange løsninger der findes.

Hvis det holdt, ville algoritmen fra OpenAI falde i det blå område fra figuren ovenfor. Og hvad ville det betyde?

• ETH ville falde og med den også SETH og hundredvis af betingede resultater, der byggede på dem. Dataloger ville skulle smide en masse »hvis ETH gælder, så …« væk eller omskrive dem.
• Problemet P versus NP ville det ikke løse. Algoritmen er stadig ikke polynomiel.
• I praksis ville der næsten ingenting ændre sig. I formlen gemmer der sig konstanter, som vi ikke kender. Hvis de var lig med én, ville $\sqrt{\ln n}$ for n = 1000 blive omkring 2,6, og vi ville få omkring 2³⁸⁰ skridt. Det er næsten det samme som 1,307¹⁰⁰⁰ ≈ 2³⁸⁶ ved nutidens bedste algoritmer. Nutidens algoritmer ville den nye først overhale tydeligt for endnu større n, og med hvor meget afhænger netop af de ukendte konstanter. Den har altså især teoretisk betydning. Kryptering og bankvæsen berører den ikke.

Indtil videre er det en ubekræftet påstand. Beviset er langt og teknisk, og eksperterne er først lige begyndt at læse det. Store meddelelser om løste problemer har tidligere mange gange vist sig at være fejlagtige, så foreløbig gælder: Vi venter og ser, hvad eksperterne siger til det. Dette afsnit skriver vi den 27. oktober 2026.

Løsning på opgaven med festen

Du skal invitere Thomas, Jens og Dennis, men ikke Karen. På figuren ses alle 16 muligheder. I hver kolonne er der én mulighed: En udfyldt cirkel betyder, at vennen kommer, en tom, at han ikke kommer. Det røde tal under kolonnen viser den første betingelse, der ikke gælder. Den eneste mulighed, hvor alle betingelser gælder, er indrammet med grønt.

Og det er netop den rå magt, som ETH anser for næsten uovervindelig: for fire venner seksten kolonner, for hundrede venner flere kolonner, end der er atomer i vores krop.

Se også

• Datalogiens største problem: P versus NP
• Udsagnslogik
• Eksponentialfunktion
• Eksponentiel vækst