Exponentiële-tijdhypothese (ETH)

Sommige opgaven kunnen we alleen oplossen door bijna alle mogelijkheden te proberen. De exponentiële-tijdhypothese, in het Engels Exponential Time Hypothesis en afgekort ETH, is de gok van informatici dat het bij één bepaalde opgave niet anders kan, hoe slim we ook zijn. Snellere methoden bestaan wel, maar zelfs de beste hebben een aantal stappen nodig dat exponentieel groeit met de grootte van de opgave.

De ETH hangt nauw samen met het probleem P versus NP, waar we een apart artikel over hebben. Als je het nog niet hebt gelezen, kijk daar dan eerst even, want we bouwen erop voort. Vooral op wat de complexiteit van een algoritme is en waarom er zo'n kloof zit tussen n² en 2ⁿ.

Wie nodig je uit voor het feest?

Je organiseert een feestje en wilt vier vrienden uitnodigen: Tim, Jeroen, Karin en Daan. Het probleem is dat er tussen hen allerlei verhoudingen bestaan en dat je graag wilt dat iedereen tevreden is. Na lang doorvragen kom je op zes voorwaarden:

Tim of Karin komt (mogelijk allebei).
Jeroen en Karin kunnen elkaar niet uitstaan, dus ze komen niet allebei.
Daan komt alleen als Jeroen ook komt.
Als Tim komt, moet ook Karin of Daan komen.
Als Tim en Karin allebei komen, moet ook Jeroen komen.
Minstens één van het trio Tim, Jeroen, Daan komt.

Wie moet je uitnodigen zodat alle voorwaarden tegelijk kloppen? Probeer het eerst zelf te bedenken, de oplossing bewaren we voor het einde van het artikel.

Informatici zouden de opgave herschrijven in de taal van de propositielogica. Elke vriend krijgt een letter, bijvoorbeeld T voor Tim. De letter is waar (Tim komt) of onwaar (Tim komt niet). Het symbool ∨ lezen we als “of” en ¬ lezen we als “niet”. De eerste voorwaarde ziet er dan zo uit:

$T \lor K$

De tweede voorwaarde zegt dat Jeroen niet komt, of Karin niet komt:

$\neg J \lor \neg K$

Bij de derde voorwaarde haal je gemakkelijk iets door elkaar. “Daan komt alleen als Jeroen ook komt” betekent dat het niet mag gebeuren dat Daan komt en Jeroen niet. Dus Daan komt niet, of Jeroen komt:

$\neg D \lor J$

Op dezelfde manier schrijven we de rest om. De hele opgave ziet er dan zo uit:

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

Kijk eens hoeveel de voorwaarden op elkaar lijken: een paar letters, sommige met het teken ¬, verbonden door het woord “of”. En geen enkele heeft meer dan drie letters. Een opgave waarin we zulke voorwaarden hebben en aan de letters waar en onwaar moeten toekennen zodat alle voorwaarden tegelijk gelden, heet 3-SAT. De drie betekent dat een voorwaarde hoogstens drie letters heeft, en SAT is de afkorting van het Engelse satisfiability, vervulbaarheid.

Op het eerste gezicht is het een spelletje voor de puzzelhoek. Maar een enorme hoeveelheid praktische opgaven is te herschrijven tot 3-SAT: lesroosters, de controle of een chip in een processor goed rekent, het plannen van diensten en ook sudoku's. Dan zijn er geen vier letters, maar zomaar miljoenen.

Hoeveel mogelijkheden moeten we proberen?

De meest directe aanpak is alles uitproberen. Tim komt of komt niet, dat zijn twee mogelijkheden. Bij elke daarvan komt Jeroen of komt hij niet, dat zijn al vier mogelijkheden. Voor vier vrienden zijn het er

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

Zo hebben we ook geredeneerd bij de binaire vectoren in het artikel over P versus NP. Met n letters kunnen we op 2ⁿ manieren waar en onwaar toekennen. Voor 4 vrienden zijn dat 16 mogelijkheden, die je in een paar minuten doorloopt. Voor 100 letters zijn het

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

mogelijkheden. Als een computer een miljard mogelijkheden per seconde zou proberen, zou hij er ongeveer drieduizend keer zoveel tijd voor nodig hebben als het heelal oud is.

Andersom is het echter makkelijk: als iemand zegt “nodig deze drie uit”, controleer je dat meteen. Je hoeft alleen de zes voorwaarden langs te lopen en bij elke te kijken of ze klopt. Een oplossing vinden is moeilijk, controleren is makkelijk. Precies zulke opgaven hebben we in het artikel over P versus NP in de klasse NP geplaatst.

Maar 3-SAT is in NP geen gewone opgave: in 1971 werd aangetoond dat elke opgave uit NP naar 3-SAT te vertalen is. Wie 3-SAT snel zou kunnen oplossen, zou dus alles snel kunnen oplossen wat snel te controleren is. Opgaven met deze eigenschap heten NP-volledig en 3-SAT is hun beroemdste vertegenwoordiger.

Kan het sneller dan 2ⁿ?

Ja. Echt alles proberen is niet nodig. Het volstaat bijvoorbeeld op te merken dat Tim niet komt: uit de eerste voorwaarde volgt dan meteen dat Karin moet komen. Alle mogelijkheden waarin geen van beiden komt, schrappen we direct. Slimme algoritmen combineren een hele reeks van zulke trucs. De beste die we nu kennen hebben ongeveer

${1,307}^{n}$

stappen nodig. Dat is een enorme sprong. Voor n = 100 komen er in plaats van 10³⁰ ongeveer 4,2 · 10¹¹ stappen uit, en dat doet een computer in een paar minuten.

Maar pas op, er zit een addertje onder het gras. 1,307ⁿ is nog steeds een exponentiële functie. We hebben het grondtal verkleind van twee naar 1,307, maar de variabele n staat nog steeds in de exponent. Als n blijft groeien, wordt het ons uiteindelijk toch te veel. Voor n = 1000 is zelfs 1,307ⁿ een getal van 117 cijfers.

En hoe zou een algoritme eruitzien dat niet exponentieel is? Bijvoorbeeld een dat toekan met n³ stappen. Dat zou polynomiaal zijn en 3-SAT zou dan in de klasse P zitten. Tussen veeltermen en exponentiële functies ligt echter nog een grijs gebied: functies die sneller groeien dan elke veelterm en toch langzamer dan elke exponentiële functie. Bijvoorbeeld

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

Hier staat in de exponent alleen de wortel van n. Laten we alle vier de functies in een tabel vergelijken:

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³⁰¹

Voor n = 1000 speelt $2^{\sqrt{n}}$ in dezelfde divisie als n³, terwijl beide exponentiële functies zijn weggelopen naar getallen waarvoor we niet eens namen hebben. Functies als $2^{\sqrt{n}}$ , die langzamer groeien dan cⁿ voor elk grondtal c groter dan één, heten subexponentieel.

Hetzelfde laat de grafiek zien. De verticale as is logaritmisch: elk streepje omhoog betekent een honderdduizend keer groter getal. Anders zou er behalve 2ⁿ niets in de afbeelding passen.

$Groei van de functies 2^n (rood), 1{,}307^n (oranje), 2^{\sqrt{n}} (blauw) en n^3 (groen) met een logaritmische verticale as$

Exponentiële functies zijn in zo'n grafiek rechte lijnen die steeds blijven stijgen. De rode 2ⁿ is steiler dan de oranje 1,307ⁿ, maar beide zijn rechte lijnen. Interessant is dat de oranje in het begin zelfs onder de groene n³ ligt. Pas rond n = 42 komt ze erboven, en dan voorgoed. De blauwe $2^{\sqrt{n}}$ buigt daarentegen af en blijft laag bij de groene.

Wat de ETH precies beweert

Nu kunnen we de hypothese formuleren. In 1999 werd ze opgesteld door Russell Impagliazzo en Ramamohan Paturi:

Er bestaat een getal c groter dan één zodat geen enkel algoritme 3-SAT met n letters sneller kan oplossen dan in ongeveer cⁿ stappen.

En in gewone taal? Het grondtal van de exponentiële functie kunnen we met slimme trucs verkleinen, van twee naar 1,5, naar 1,307, misschien ooit naar 1,2. Maar we drukken het nooit willekeurig dicht bij één. Ergens ligt een grens waaronder het niet kan. Een algoritme met complexiteit $2^{\sqrt{n}}$ zou volgens de ETH dus niet moeten bestaan.

Waarom een hypothese? Omdat niemand het kan bewijzen. De ETH is een werkaanname, net zoals we in het artikel over P versus NP aannemen dat P ≠ NP. De meeste informatici geloven erin, omdat tientallen jaren van pogingen alleen hebben opgeleverd dat het grondtal langzaam van twee naar beneden kruipt. Een bewijs heeft echter niemand in handen.

ETH en P versus NP

Hoe hangen deze twee vragen samen? Stel je voor dat 3-SAT een “echte” moeilijkheid heeft, namelijk het snelst mogelijke algoritme. Dat kan in drie zones liggen:

Drie zones van moeilijkheid van 3-SAT: polynomiaal (groen), subexponentieel (blauw) en exponentieel (rood)

Groene zone, polynomiaal. 3-SAT is bijvoorbeeld in n³ stappen op te lossen. Omdat 3-SAT NP-volledig is, zou dan P = NP gelden en de ETH zou natuurlijk niet kloppen.
Blauwe zone, subexponentieel. 3-SAT is op te lossen in $2^{\sqrt{n}}$ stappen of iets dergelijks. Polynomiaal niet, dus geldt P ≠ NP. Maar de ETH zou niet kloppen.
Rode zone, exponentieel. Beter dan cⁿ kan het niet. De ETH geldt, en daarmee geldt ook P ≠ NP.

Aan de afbeelding zie je dat de ETH een sterkere bewering is dan P ≠ NP. Ze zegt niet alleen dat 3-SAT niet polynomiaal op te lossen is, maar ook niet subexponentieel. Wie de ETH zou bewijzen, bewijst daarmee ook P ≠ NP en krijgt een miljoen dollar.

En andersom: wie de ETH zou weerleggen, heeft daarmee nog niet P = NP bewezen. Een algoritme uit de blauwe zone is voldoende. Onthoud dit, we gebruiken het zo meteen.

Waar is de ETH goed voor?

Bewijzen dat een opgave niet snel op te lossen is, is in de informatica ontzettend moeilijk. Bijna niets van dien aard kunnen we. De ETH geeft ons een achterdeur: in plaats van “opgave X is moeilijk” bewijzen we “opgave X is moeilijk, als de ETH geldt”.

Hoe? We laten zien dat als opgave X snel op te lossen was, ook 3-SAT snel op te lossen zou zijn. Neem bijvoorbeeld deze: we hebben n mensen en van sommige paren weten we dat ze elkaar niet kunnen uitstaan. We willen ze over drie kamers verdelen zodat zo'n paar niet in dezelfde kamer terechtkomt. Informatici noemen dat het kleuren van een graaf met drie kleuren. Uit elke 3-SAT-opgave is ze zo te construeren dat het aantal mensen slechts een veelvoud van het aantal letters is. Als de mensen dus subexponentieel over de kamers te verdelen waren, was ook 3-SAT subexponentieel op te lossen en zou de ETH vallen.

Zulke voorwaardelijke resultaten zijn er tegenwoordig honderden. Het hele vakgebied dat onderzoekt hoe moeilijk afzonderlijke opgaven precies zijn, staat op de ETH als een huis op zijn fundament.

De ETH heeft ook een sterkere zus, de sterke exponentiële-tijdhypothese (SETH). Die richt zich op opgaven waarin de voorwaarden meer dan drie letters mogen hebben, bijvoorbeeld tien of honderd. De SETH beweert dat het best mogelijke grondtal dichter bij twee komt naarmate we langere voorwaarden toestaan. Bij lange voorwaarden zou je dus bijna niets kunnen besparen ten opzichte van het domme uitproberen van alle 2ⁿ mogelijkheden.

Waarom er nu over de ETH wordt gepraat

Het bedrijf OpenAI, dat je vooral kent van ChatGPT, heeft in oktober 2026 een preprint gepubliceerd, dus een artikel dat nog niet is beoordeeld. Het heet The Exponential Time Hypothesis is False, in het Nederlands “De exponentiële-tijdhypothese is onjuist”. Daarin beweert het bedrijf een algoritme te hebben gevonden dat 3-SAT oplost in ongeveer

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

stappen. In de exponent staat dus niet n alleen, maar n gedeeld door de wortel van de (natuurlijke) logaritme. Die noemer groeit verschrikkelijk langzaam, maar hij groeit, en dat is genoeg om de functie subexponentieel te maken. Het algoritme zou zelfs niet alleen één oplossing kunnen vinden, maar ook kunnen tellen hoeveel oplossingen er zijn.

Als dat klopte, zou het algoritme van OpenAI in de blauwe zone uit de afbeelding hierboven vallen. En wat zou dat betekenen?

De ETH zou vallen en daarmee ook de SETH en honderden voorwaardelijke resultaten die erop steunden. Informatici zouden veel “als de ETH geldt, dan …” moeten weggooien of herschrijven.
Het probleem P versus NP zou het niet oplossen. Het algoritme is nog steeds niet polynomiaal.
In de praktijk zou er bijna niets veranderen. In de formule zitten constanten die we niet kennen. Als ze gelijk aan één waren, zou $\sqrt{\ln n}$ voor n = 1000 ongeveer 2,6 zijn en kregen we ongeveer 2³⁸⁰ stappen. Dat is bijna hetzelfde als 1,307¹⁰⁰⁰ ≈ 2³⁸⁶ bij de beste algoritmen van nu. De huidige algoritmen zou het nieuwe pas bij nog grotere n duidelijk inhalen, en met hoeveel hangt juist af van de onbekende constanten. Het heeft dus vooral theoretische betekenis. Versleuteling en bankieren worden er niet door geraakt.

Tot nu toe is het een onbevestigde bewering. Het bewijs is lang en technisch en de deskundigen beginnen het pas te lezen. Grote aankondigingen van opgeloste problemen zijn in het verleden al vaak onjuist gebleken, dus voorlopig geldt: we wachten af wat de deskundigen ervan zeggen. Deze alinea schrijven we op 27 oktober 2026.

Oplossing van de opgave met het feest

Uitnodigen moet je Tim, Jeroen en Daan, Karin niet. In de afbeelding staan alle 16 mogelijkheden. In elke kolom staat één mogelijkheid: een gevulde cirkel betekent dat de vriend komt, een lege dat hij niet komt. Het rode getal onder de kolom toont de eerste voorwaarde die niet klopt. De enige mogelijkheid waarbij alle voorwaarden kloppen, is groen omrand.

Alle 16 mogelijkheden wie je kunt uitnodigen. De rijen horen bij de vrienden T, J, K, D, een gevulde cirkel betekent dat hij komt.

En dit is precies de brute kracht die de ETH als bijna onverslaanbaar beschouwt: voor vier vrienden zestien kolommen, voor honderd vrienden meer kolommen dan er atomen in ons lichaam zitten.

Zie ook

« Vorige: Het grootste probleem in de informatica: P versus NP

Volgende: De methode van Trachtenberg voor snel optellen »