Exponenciális idő hipotézis (ETH)

Néhány feladatot csak úgy tudunk megoldani, hogy szinte az összes lehetőséget kipróbáljuk. Az exponenciális idő hipotézis, angolul Exponential Time Hypothesis, röviden ETH, az informatikusok fogadása arra, hogy egy bizonyos feladatnál nem megy másként, bármilyen okosak vagyunk is. Gyorsabb módszerek léteznek, de még a legjobbaknak is olyan lépésszám kell, amely a feladat méretével exponenciálisan nő.

Az ETH szorosan kapcsolódik a P versus NP problémához, amelyről külön cikkünk van. Ha még nem olvastad, nézz be előbb oda, mert arra építünk. Főleg arra, mi az algoritmus bonyolultsága, és miért olyan szakadék tátong n² és 2ⁿ között.

Kit hívjunk meg a bulira

Bulit szervezel, és négy barátodat szeretnéd meghívni: Tamást, Jánost, Katát és Dávidot. A bökkenő az, hogy köztük különféle viszonyok vannak, te pedig azt szeretnéd, hogy mindenki elégedett legyen. Hosszas puhatolózás után hat feltétel jön ki:

1. Tamás vagy Kata eljön (akár mindketten).
2. János és Kata nem bírják egymást, ezért nem jönnek el mindketten.
3. Dávid csak akkor jön el, ha János is eljön.
4. Ha Tamás eljön, akkor Katának vagy Dávidnak is el kell jönnie.
5. Ha Tamás és Kata is eljön, akkor Jánosnak is el kell jönnie.
6. Tamás, János, Dávid közül legalább az egyik eljön.

Kit hívj meg, hogy az összes feltétel egyszerre teljesüljön? Próbáld kitalálni magad, a megoldást a cikk végére tartogatjuk.

Az informatikusok a feladatot az ítéletlogika nyelvére írnák át. Minden barát kap egy betűt, a könnyebbség kedvéért a nevek latin kezdőbetűit: T mint Tamás, J mint János, K mint Kata, D mint Dávid. A betű vagy igaz (Tamás eljön), vagy hamis (Tamás nem jön el). A ∨ jelet „vagy”-nak olvassuk, a ¬ jelet „nem”-nek. Az első feltétel ekkor így néz ki:

$$T\vee K$$

A második feltétel azt mondja, hogy János nem jön el, vagy Kata nem jön el:

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

A harmadiknál könnyű eltéveszteni. „Dávid csak akkor jön el, ha János is eljön” azt jelenti, hogy nem fordulhat elő, hogy Dávid eljön, János pedig nem. Vagyis vagy Dávid nem jön el, vagy János eljön:

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

Ugyanígy írjuk át a többit is. Az egész feladat ekkor így néz ki:

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

Nézd meg, mennyire hasonlítanak egymásra a feltételek: néhány betű, némelyik ¬ jellel, a „vagy” szóval összekötve. És egyiknek sincs háromnál több betűje. Azt a feladatot, amelyben ilyen feltételeink vannak, és azt keressük, hogyan rendeljünk a betűkhöz igazat és hamisat úgy, hogy az összes feltétel egyszerre teljesüljön, 3-SAT-nak hívják. A hármas azt jelenti, hogy egy feltételben legfeljebb három betű van, a SAT pedig az angol satisfiability, vagyis kielégíthetőség rövidítése.

Elsőre ez csak egy játék a szórakoztató rovatba. Csakhogy 3-SAT alakra hatalmas mennyiségű gyakorlati feladat átírható: órarendek, annak ellenőrzése, hogy egy processzorban a chip helyesen számol, műszakbeosztás és még a sudoku is. Ilyenkor nem négy betű van, hanem akár milliónyi.

Hány lehetőséget kell kipróbálni?

A legkézenfekvőbb módszer az, hogy mindent kipróbálunk. Tamás eljön vagy nem jön el, ez két lehetőség. Mindegyik esetben János eljön vagy nem, ez már négy lehetőség. Négy barátnál ez

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

Ugyanígy gondolkodtunk a bináris vektoroknál a P versus NP cikkben. Ha n betűnk van, az igazat és a hamisat 2ⁿ módon rendelhetjük hozzájuk. 4 barátnál ez 16 lehetőség, amelyeket pár perc alatt átnézel. 100 betűnél ez

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

lehetőség. Ha egy számítógép másodpercenként egymilliárd lehetőséget próbálna ki, nagyjából háromezerszer annyi időre lenne szüksége, mint amennyi ideje az Univerzum létezik.

Visszafelé viszont könnyű: ha valaki azt mondja neked, „hívd meg ezt a hármat”, azonnal ellenőrizheted. Elég végigmenni a hat feltételen, és mindegyiknél megnézni, teljesül-e. A megoldást megtalálni nehéz, ellenőrizni könnyű. Pontosan az ilyen feladatokat soroltuk a P versus NP cikkben az NP osztályba.

Csakhogy a 3-SAT nem akármilyen feladat az NP-ben: 1971-ben kiderült, hogy a 3-SAT-ra az NP bármelyik feladata visszavezethető. Aki tehát gyorsan meg tudná oldani a 3-SAT-ot, az gyorsan megoldana mindent, ami gyorsan ellenőrizhető. Az ilyen tulajdonságú feladatokat NP-teljesnek nevezzük, és a 3-SAT a leghíresebb képviselőjük.

Megy ez gyorsabban is, mint 2ⁿ?

Megy. Teljesen mindent kipróbálni felesleges. Elég például észrevenni, hogy Tamás nem jön el: az első feltételből ekkor rögtön következik, hogy Katának el kell jönnie. Az összes olyan lehetőséget, amelyben egyikük sem jönne el, azonnal kihúzzuk. Az okos algoritmusok sok ilyen trükköt kombinálnak. A ma ismert legjobbaknak nagyjából

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

lépés kell. Ez óriási ugrás. n = 100-nál 10³⁰ helyett nagyjából 4,2 · 10¹¹ lépés jön ki, amelyet a számítógép pár perc alatt elvégez.

De vigyázat, itt a csapda. Az 1,307ⁿ még mindig exponenciális függvény. Az alapot kettőről 1,307-re csökkentettük, de az n változó a kitevőben maradt. Ha n tovább nő, végül úgyis agyonnyom minket. n = 1000-nél már az 1,307ⁿ is egy 117 jegyű szám.

És hogyan nézne ki egy olyan algoritmus, amely nem exponenciális? Például olyan, amelynek elég n³ lépés. Az polinomiális lenne, és a 3-SAT ekkor a P osztályba tartozna. A polinomok és az exponenciális függvények között azonban van még egy szürke zóna: azok a függvények, amelyek gyorsabban nőnek bármelyik polinomnál, mégis lassabban bármelyik exponenciális függvénynél. Például

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

Itt a kitevőben csak n négyzetgyöke áll. Hasonlítsuk össze mind a négy függvényt egy táblázatban:

n = 1000-nél a $2^{\sqrt{n}}$ ugyanabban a súlycsoportban van, mint az n³, miközben mindkét exponenciális függvény olyan számokba szaladt el, amelyeknek még nevünk sincs. Az olyan függvényeket, mint a $2^{\sqrt{n}}$, amelyek bármely egynél nagyobb c alapra lassabban nőnek, mint a cⁿ, szubexponenciálisnak nevezzük.

Ugyanezt mutatja a grafikon is. A függőleges tengely logaritmikus: minden egyes osztás felfelé százezerszer nagyobb számot jelent. Különben az ábrán a 2ⁿ-en kívül semmi nem férne el.

Az exponenciális függvények egy ilyen grafikonon egyenesek, amelyek folyamatosan emelkednek. A piros 2ⁿ meredekebb, mint a narancssárga 1,307ⁿ, de mindkettő egyenes. Érdekes, hogy a narancssárga az elején még a zöld n³ alatt is fekszik. Csak n = 42 körül előzi meg, de akkor már örökre. A kék $2^{\sqrt{n}}$ ezzel szemben elhajlik, és lent marad a zöld közelében.

Mit állít pontosan az ETH

Most már kimondhatjuk a hipotézist. 1999-ben Russell Impagliazzo és Ramamohan Paturi fogalmazta meg:

Létezik egynél nagyobb c szám úgy, hogy egyetlen algoritmus sem tudja megoldani az n betűs 3-SAT-ot nagyjából cⁿ lépésnél gyorsabban.

És emberi nyelven? Az exponenciális függvény alapját okos trükkökkel tudjuk csökkenteni, kettőről 1,5-re, 1,307-re, talán egyszer 1,2-re. De soha nem szorítjuk tetszőlegesen közel az egyhez. Valahol van egy határ, amely alatt nem megy. A $2^{\sqrt{n}}$ bonyolultságú algoritmus tehát az ETH szerint nem kellene, hogy létezzen.

Miért hipotézis? Mert senki sem tudja bebizonyítani. Az ETH munkahipotézis, ahogy a P versus NP cikkben is feltételezzük, hogy P ≠ NP. A legtöbb informatikus hisz benne, mert évtizedek erőfeszítése csak annyit hozott, hogy az alap lassan csúszik lefelé a kettőről. Bizonyítéka viszont senkinek sincs a kezében.

Az ETH és a P versus NP

Hogyan függ össze ez a két kérdés? Képzeld el, hogy a 3-SAT-nak van valamilyen „igazi” nehézsége, a lehető leggyorsabb algoritmus. Ez három sáv valamelyikébe eshet:

• Zöld sáv, polinomiális. A 3-SAT megoldható mondjuk n³ lépésben. Mivel a 3-SAT NP-teljes, ekkor P = NP igaz lenne, az ETH pedig természetesen nem.
• Kék sáv, szubexponenciális. A 3-SAT megoldható $2^{\sqrt{n}}$ lépésben vagy valami hasonlóban. Polinomiálisan nem, tehát P ≠ NP igaz. De az ETH nem lenne igaz.
• Piros sáv, exponenciális. cⁿ-nél jobban nem megy. Az ETH igaz, és ezáltal P ≠ NP is igaz.

Az ábráról látszik, hogy az ETH erősebb állítás, mint a P ≠ NP. Nemcsak azt mondja, hogy a 3-SAT nem oldható meg polinomiálisan, hanem azt is, hogy még szubexponenciálisan sem. Aki bebizonyítaná az ETH-t, azzal a P ≠ NP-t is bebizonyítaná, és megkapna egymillió dollárt.

És fordítva: aki az ETH-t megcáfolná, azzal még nem feltétlenül bizonyítaná be a P = NP-t. Neki elég egy algoritmus a kék sávból. Ezt jegyezd meg, mindjárt kihasználjuk.

Mire jó az ETH

Bebizonyítani, hogy egy feladat nem oldható meg gyorsan, az informatikában hihetetlenül nehéz. Szinte semmi ilyesmit nem tudunk. Az ETH egy hátsó ajtót ad nekünk: ahelyett, hogy „az X feladat nehéz”, azt bizonyítjuk, hogy „az X feladat nehéz, ha igaz az ETH”.

Hogyan? Megmutatjuk, hogy ha az X feladat gyorsan megoldható lenne, a 3-SAT is gyorsan megoldható lenne. Vegyük például ezt: van n emberünk, és néhány párról tudjuk, hogy nem bírják egymást. Három szobába szeretnénk őket szétosztani úgy, hogy egyik ilyen pár se kerüljön ugyanabba a szobába. Az informatikusok ezt gráf három színnel való színezésének hívják. Bármelyik 3-SAT feladatból megszerkeszthető egy ilyen feladat úgy, hogy az emberek száma csak a betűk számának néhányszorosa legyen. Ha tehát az embereket szubexponenciálisan szét lehetne osztani a szobákba, szubexponenciálisan meg lehetne oldani a 3-SAT-ot is, és az ETH megdőlne.

Az ilyen feltételes eredményekből ma már több száz van. Az egész terület, amely azt vizsgálja, pontosan mennyire nehezek az egyes feladatok, az ETH-n áll, mint a ház az alapjain.

Az ETH-nak van egy erősebb testvére is, az erős exponenciális idő hipotézis (SETH). Ez azokra a feladatokra vonatkozik, ahol a feltételekben háromnál több betű lehet, mondjuk tíz vagy száz. A SETH azt állítja, hogy minél hosszabb feltételeket engedünk meg, annál jobban megközelíti a lehető legjobb alap a kettőt. Hosszú feltételeknél tehát szinte semmit sem lehetne megspórolni az összes 2ⁿ lehetőség ostoba kipróbálásához képest.

Miért beszélnek most az ETH-ról

Az OpenAI cég, amelyet főleg a ChatGPT miatt ismersz, 2026 októberében közzétett egy preprintet, vagyis olyan cikket, amely még nem esett át szakmai bírálaton. A címe The Exponential Time Hypothesis is False, magyarul „Az exponenciális idő hipotézis hamis”. Azt állítja benne, hogy talált egy algoritmust, amely a 3-SAT-ot nagyjából

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

lépésben oldja meg. A kitevőben tehát nem maga az n áll, hanem az n osztva a (természetes) logaritmus négyzetgyökével. Ez a nevező rettentően lassan nő, de nő, és ez elég ahhoz, hogy a függvény szubexponenciális legyen. Az algoritmus állítólag nemcsak egy megoldást tud megtalálni, hanem megszámolni is, hány megoldás létezik.

Ha ez igaz lenne, az OpenAI algoritmusa a fenti ábra kék sávjába esne. És mit jelentene ez?

• Az ETH megdőlne, vele együtt a SETH és a több száz feltételes eredmény, amely rájuk épült. Az informatikusoknak rengeteg „ha igaz az ETH, akkor…” állítást kellene eldobniuk vagy átírniuk.
• A P versus NP problémát ez nem oldaná meg. Az algoritmus még mindig nem polinomiális.
• A gyakorlatban szinte semmi nem változna. A képletben ismeretlen állandók rejtőznek. Ha egyenlők lennének eggyel, n = 1000-re a $\sqrt{\ln n}$ nagyjából 2,6 jön ki, és nagyjából 2³⁸⁰ lépést kapnánk. Ez majdnem ugyanannyi, mint az 1,307¹⁰⁰⁰ ≈ 2³⁸⁶ a mai legjobb algoritmusoknál. A mai algoritmusokat az új csak még nagyobb n-ekre előzné meg érezhetően, és hogy mennyivel, az éppen az ismeretlen állandóktól függ. Így főleg elméleti jelentősége van. A titkosítást vagy a bankrendszert nem érinti.

Egyelőre ellenőrizetlen állításról van szó. A bizonyítás hosszú és technikai, a szakemberek most kezdik olvasni. A megoldott problémákról szóló nagy bejelentések a múltban már sokszor hibásnak bizonyultak, ezért egyelőre az érvényes: megvárjuk, mit mondanak rá a szakértők. Ezt a bekezdést 2026. október 27-én írjuk.

A bulis feladat megoldása

Tamást, Jánost és Dávidot kell meghívnod, Katát nem. Az ábrán mind a 16 lehetőség látható. Minden oszlopban egy lehetőség van: a teli karika azt jelenti, hogy a barát eljön, az üres azt, hogy nem jön el. Az oszlop alatti piros szám az első olyan feltételt mutatja, amely nem teljesül. Az egyetlen lehetőséget, amelynél minden feltétel teljesül, zöld keret veszi körül.

És pontosan ez az a nyers erő, amelyet az ETH szinte legyőzhetetlennek tart: négy barátnál tizenhat oszlop, száz barátnál több oszlop, mint ahány atom van a testünkben.

Lásd még

• Az informatika legnagyobb problémája: P versus NP
• Ítéletlogika
• Exponenciális függvény
• Exponenciális növekedés