Hypotéza exponenciálního času (ETH)

Některé úlohy umíme vyřešit jen tak, že vyzkoušíme skoro všechny možnosti. Hypotéza exponenciálního času, anglicky Exponential Time Hypothesis a zkráceně ETH, je sázka informatiků, že u jedné konkrétní úlohy to jinak nepůjde, ať budeme sebechytřejší. Rychlejší postupy existují, jenže i ty nejlepší budou potřebovat počet kroků, který s velikostí úlohy roste exponenciálně.

ETH úzce souvisí s problémem P versus NP, o kterém máme samostatný článek. Pokud jste ho nečetli, mrkněte nejdřív tam, budeme na něm stavět. Hlavně na tom, co je složitost algoritmu a proč je mezi n² a 2ⁿ taková propast.

Koho pozvat na oslavu

Chystáte oslavu a chcete pozvat čtyři kamarády: Tomáše, Jindru, Kláru a Dádu. Háček je v tom, že mezi nimi panují různé vztahy a vy byste rádi, aby byli spokojení všichni. Po dlouhém vyptávání vám vyjde šest podmínek:

1. Přijde Tomáš, nebo Klára (klidně i oba).
2. Jindra a Klára se nesnesou, takže nepřijdou oba.
3. Dáda přijde jen tehdy, když přijde i Jindra.
4. Když přijde Tomáš, musí přijít i Klára, nebo Dáda.
5. Když přijdou Tomáš i Klára, musí přijít i Jindra.
6. Přijde aspoň jeden z trojice Tomáš, Jindra, Dáda.

Koho pozvat, aby platily všechny podmínky najednou? Zkuste to vymyslet sami, řešení schováváme na konec článku.

Informatici by si úlohu přepsali do řeči výrokové logiky. Každý kamarád dostane jedno písmeno, třeba T jako Tomáš. Písmeno je buď pravdivé (Tomáš přijde), nebo nepravdivé (Tomáš nepřijde). Symbol ∨ čteme „nebo“ a ¬ čteme „ne“. První podmínka pak vypadá takto:

$$T\vee K$$

Druhá podmínka říká, že nepřijde Jindra, nebo nepřijde Klára:

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

U třetí podmínky se snadno spletete. „Dáda přijde jen tehdy, když přijde i Jindra“ znamená, že se nesmí stát, aby Dáda přišel a Jindra ne. Tedy buď Dáda nepřijde, nebo přijde Jindra:

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

Stejným způsobem přepíšeme i zbytek. Celá úloha pak vypadá takto:

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

Podívejte se, jak jsou si podmínky podobné: několik písmen, některá se znaménkem ¬, spojených slovem „nebo“. A žádná z nich nemá víc než tři písmena. Úloze, kde máme takové podmínky a hledáme, jak písmenům přiřadit pravdu a nepravdu, aby platily všechny najednou, se říká 3-SAT. Trojka znamená, že podmínka má nejvýš tři písmena, a SAT je zkratka anglického satisfiability, splnitelnost.

Na první pohled je to hříčka do zábavného koutku. Jenže do tvaru 3-SAT jde přepsat obrovské množství praktických úloh: rozvrhy hodin, kontrolu, že čip v procesoru počítá správně, plánování směn i sudoku. Písmen pak nejsou čtyři, ale klidně miliony.

Kolik možností je potřeba zkusit?

Nejpřímočařejší postup je vyzkoušet všechno. Tomáš přijde, nebo nepřijde, to jsou dvě možnosti. Pro každou z nich přijde, nebo nepřijde Jindra, to už jsou čtyři možnosti. Pro čtyři kamarády je jich

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

Stejně jsme uvažovali u binárních vektorů v článku o P vs. NP. Máme-li n písmen, můžeme jim pravdu a nepravdu přiřadit 2ⁿ způsoby. Pro 4 kamarády je to 16 možností, které projdete za pár minut. Pro 100 písmen je to

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

možností. Kdyby počítač zkoušel miliardu možností za sekundu, potřeboval by na to zhruba třítisíckrát víc času, než kolik existuje vesmír.

Jenže obráceně je to snadné: když vám někdo řekne „pozvi tyhle tři“, ověříte to hned. Stačí projít šest podmínek a u každé se podívat, jestli platí. Najít řešení je těžké, zkontrolovat ho je snadné. Přesně takové úlohy jsme v článku o P vs. NP zařadili do třídy NP.

Jenže 3-SAT není v NP ledajaká úloha: v roce 1971 se ukázalo, že do 3-SATu jde přeložit každou úlohu z NP. Kdo by tedy 3-SAT zvládal rychle, zvládal by rychle úplně všechno, co jde rychle ověřit. Úlohám s touhle vlastností se říká NP-úplné a 3-SAT je jejich nejslavnějším zástupcem.

Jde to rychleji než 2ⁿ?

Jde. Zkoušet úplně všechno je zbytečné. Stačí si třeba všimnout, že Tomáš nepřijde: z první podmínky pak hned plyne, že přijít musí Klára. Všechny možnosti, kde by nepřišel ani jeden z nich, rovnou škrtneme. Chytré algoritmy takových triků kombinují celou řadu. Ty nejlepší dnes známé potřebují zhruba

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

kroků. To je obrovský skok. Pro n = 100 vychází místo 10³⁰ zhruba 4,2 · 10¹¹ kroků, což počítač zvládne za pár minut.

Ale pozor, zrada. 1,307ⁿ je pořád exponenciální funkce. Zmenšili jsme základ ze dvojky na 1,307, ale proměnná n zůstala v exponentu. Když n dál poroste, nakonec nás to stejně převálcuje. Pro n = 1000 je i 1,307ⁿ číslo se 117 číslicemi.

A jak by vypadal algoritmus, který exponenciální není? Třeba takový, který si vystačí s n³ kroky. Byl by polynomiální a 3-SAT by pak patřil do třídy P. Mezi polynomy a exponenciálami ale leží ještě šedá zóna: funkce, které rostou rychleji než každý polynom, a přesto pomaleji než každá exponenciála. Třeba

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

Tady je v exponentu jen odmocnina z n. Porovnejme si všechny čtyři funkce v tabulce:

Pro n = 1000 je $2^{\sqrt{n}}$ ve stejné lize jako n³, kdežto obě exponenciály utekly do čísel, pro která nemáme ani jména. Funkcím jako $2^{\sqrt{n}}$, které rostou pomaleji než cⁿ pro jakýkoli základ c větší než jedna, se říká subexponenciální.

Totéž ukazuje graf. Svislá osa je logaritmická: každý dílek nahoru znamená stotisíckrát větší číslo. Jinak by se do obrázku nic kromě 2ⁿ nevešlo.

Exponenciály jsou v takovém grafu přímky, které pořád stoupají. Červená 2ⁿ je strmější než oranžová 1,307ⁿ, ale obě jsou přímky. Zajímavé je, že oranžová zpočátku leží dokonce pod zelenou n³. Předběhne ji až kolem n = 42, pak už ale nadobro. Modrá $2^{\sqrt{n}}$ se naopak ohýbá a drží se dole u zelené.

Co přesně ETH tvrdí

Teď už můžeme hypotézu vyslovit. V roce 1999 ji zformulovali Russell Impagliazzo a Ramamohan Paturi:

Existuje číslo c větší než jedna takové, že žádný algoritmus neumí vyřešit 3-SAT s n písmeny rychleji než zhruba za cⁿ kroků.

A lidsky? Základ exponenciály umíme chytrými triky zmenšovat, ze dvojky na 1,5, na 1,307, možná jednou na 1,2. Ale nikdy ho nestlačíme libovolně blízko k jedničce. Někde je hranice, pod kterou to nejde. Algoritmus se složitostí $2^{\sqrt{n}}$ by tedy podle ETH existovat neměl.

Proč hypotéza? Protože to nikdo neumí dokázat. ETH je pracovní předpoklad, podobně jako v článku o P vs. NP předpokládáme, že P ≠ NP. Většina informatiků jí věří, protože desítky let snažení přinesly jen to, že se základ pomalu plíží z dvojky dolů. Důkaz ale nikdo v ruce nemá.

ETH a P vs. NP

Jak spolu tyhle dvě otázky souvisí? Představte si, že 3-SAT má nějakou „skutečnou“ obtížnost, nejrychlejší možný algoritmus. Ten může ležet ve třech pásmech:

• Zelené pásmo, polynomiální. 3-SAT jde vyřešit třeba za n³ kroků. Protože je 3-SAT NP-úplný, platilo by pak P = NP a ETH by samozřejmě neplatila.
• Modré pásmo, subexponenciální. 3-SAT jde vyřešit za $2^{\sqrt{n}}$ kroků nebo něco podobného. Polynomiálně ne, takže platí P ≠ NP. Ale ETH by neplatila.
• Červené pásmo, exponenciální. Lepší než cⁿ to nejde. ETH platí, a tím pádem platí i P ≠ NP.

Z obrázku je vidět, že ETH je silnější tvrzení než P ≠ NP. Říká nejen, že 3-SAT nejde vyřešit polynomiálně, ale že nejde vyřešit ani subexponenciálně. Kdo by dokázal ETH, dokázal by tím i P ≠ NP a získal by milion dolarů.

A obráceně: kdo by ETH vyvrátil, nemusel tím ještě dokázat P = NP. Stačí mu algoritmus z modrého pásma. Tohle si zapamatujte, za chvíli to využijeme.

K čemu je ETH dobrá

Dokázat, že nějaká úloha nejde vyřešit rychle, je v informatice neskutečně těžké. Skoro nic takového neumíme. ETH nám dává zadní vrátka: místo „úloha X je těžká“ dokážeme „úloha X je těžká, pokud platí ETH“.

Jak? Ukážeme, že kdyby šla rychle vyřešit úloha X, šel by rychle vyřešit i 3-SAT. Vezměme třeba tuhle: máme n lidí a o některých dvojicích víme, že se nesnesou. Chceme je rozdělit do tří místností tak, aby žádná taková dvojice neskončila ve stejné místnosti. Informatici jí říkají obarvení grafu třemi barvami. Z každé úlohy 3-SAT ji jde sestrojit tak, že počet lidí vyjde jen několikanásobkem počtu písmen. Kdyby tedy šlo rozdělit lidi do místností subexponenciálně, šlo by subexponenciálně řešit i 3-SAT a ETH by padla.

Takových podmíněných výsledků jsou dnes stovky. Celý obor, který zkoumá, jak přesně těžké jednotlivé úlohy jsou, stojí na ETH jako dům na základech.

ETH má i silnější sestru, silnou hypotézu exponenciálního času (SETH). Ta se zaměřuje na úlohy, kde podmínky smějí mít víc než tři písmena, třeba deset nebo sto. SETH tvrdí, že čím delší podmínky povolíme, tím víc se nejlepší možný základ blíží dvojce. Pro dlouhé podmínky by tedy nešlo ušetřit skoro nic proti hloupému zkoušení všech 2ⁿ možností.

Proč se o ETH teď mluví

Společnost OpenAI, kterou znáte hlavně díky ChatGPT, zveřejnila v říjnu 2026 preprint, tedy článek, který zatím neprošel recenzí. Jmenuje se The Exponential Time Hypothesis is False, česky „Hypotéza exponenciálního času neplatí“. Tvrdí v něm, že našla algoritmus, který řeší 3-SAT zhruba za

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

kroků. V exponentu tedy nestojí samotné n, ale n vydělené odmocninou z (přirozeného) logaritmu. Ten jmenovatel roste strašně pomalu, ale roste, a to stačí, aby funkce byla subexponenciální. Algoritmus prý dokonce umí nejen najít jedno řešení, ale spočítat, kolik řešení existuje.

Kdyby to platilo, spadal by algoritmus od OpenAI do modrého pásma z obrázku výš. A co by to znamenalo?

• ETH by padla a s ní i SETH a stovky podmíněných výsledků, které na nich stály. Informatici by museli spoustu „pokud platí ETH, pak…“ zahodit nebo přepsat.
• Problém P versus NP by to nevyřešilo. Algoritmus pořád není polynomiální.
• V praxi by se skoro nic nezměnilo. Ve vzorci se skrývají konstanty, které neznáme. Kdyby byly rovné jedné, pro n = 1000 vyjde $\sqrt{\ln n}$ zhruba 2,6 a dostali bychom zhruba 2³⁸⁰ kroků. To je skoro totéž jako 1,307¹⁰⁰⁰ ≈ 2³⁸⁶ u dnešních nejlepších algoritmů. Dnešní algoritmy by nový výrazně předstihl až pro ještě větší n a o kolik, záleží právě na neznámých konstantách. Má tedy hlavně teoretický význam. Šifrování ani bankovnictví se to netýká.

Zatím jde o neověřené tvrzení. Důkaz je dlouhý a technický a odborníci ho teprve začínají číst. Velká oznámení o vyřešených problémech se v minulosti už mnohokrát ukázala jako chybná, takže zatím platí: počkáme si, co na to řeknou odborníci. Tenhle odstavec píšeme 27. října 2026.

Řešení úlohy s oslavou

Pozvat máte Tomáše, Jindru a Dádu, Kláru ne. Na obrázku je všech 16 možností. V každém sloupečku je jedna možnost: plný kroužek znamená, že kamarád přijde, prázdný, že nepřijde. Červené číslo pod sloupečkem ukazuje první podmínku, která neplatí. Jediná možnost, u které platí všechny podmínky, je orámovaná zeleně.

A přesně tohle je hrubá síla, kterou ETH považuje za skoro nepřekonatelnou: pro čtyři kamarády šestnáct sloupečků, pro sto kamarádů víc sloupečků, než je atomů v našem těle.

Viz také

• Největší problém v informatice: P versus NP
• Výroková logika
• Exponenciální funkce
• Exponenciální růst