Eksponenttiaikahypoteesi (ETH)

Joitakin tehtäviä voimme ratkaista vain kokeilemalla lähes kaikkia vaihtoehtoja. Eksponenttiaikahypoteesi, englanniksi Exponential Time Hypothesis ja lyhyesti ETH, on tietojenkäsittelytieteilijöiden veto siitä, että yhden tietyn tehtävän kohdalla ei voi tehdä toisin, olimmepa kuinka fiksuja tahansa. Nopeampia menetelmiä on olemassa, mutta jopa parhaat tarvitsevat askelmäärän, joka kasvaa eksponentiaalisesti tehtävän koon mukana.

ETH liittyy läheisesti P vs. NP -ongelmaan, josta meillä on oma artikkeli. Jos et ole lukenut sitä, vilkaise ensin sinne, sillä rakennamme sen varaan. Etenkin siihen, mitä algoritmin kompleksisuus on ja miksi lukujen n² ja 2ⁿ välillä on niin valtava kuilu.

Keitä kutsut juhliin

Suunnittelet juhlia ja haluat kutsua neljä kaveria: Tomin, Jarin, Kaisan ja Danielin. Ongelma on, että heidän välillään vallitsee erilaisia suhteita, ja haluaisit kaikkien olevan tyytyväisiä. Pitkän kyselyn jälkeen päädyt kuuteen ehtoon:

Tomi tai Kaisa tulee (vaikka molemmat).
Jari ja Kaisa eivät siedä toisiaan, joten he eivät tule molemmat.
Daniel tulee vain, jos myös Jari tulee.
Jos Tomi tulee, myös Kaisan tai Danielin on tultava.
Jos sekä Tomi että Kaisa tulevat, myös Jarin on tultava.
Ainakin yksi kolmikosta Tomi, Jari, Daniel tulee.

Keitä sinun pitää kutsua, jotta kaikki ehdot pätevät yhtä aikaa? Yritä keksiä se itse, ratkaisun säästämme artikkelin loppuun.

Tietojenkäsittelytieteilijät kirjoittaisivat tehtävän uudelleen propositiologiikan kielelle. Jokainen kaveri saa kirjaimen, esimerkiksi T Tomille. Kirjain on joko tosi (Tomi tulee) tai epätosi (Tomi ei tule). Symbolin ∨ luemme ”tai” ja symbolin ¬ luemme ”ei”. Ensimmäinen ehto näyttää silloin tältä:

$T \lor K$

Toinen ehto sanoo, että Jari ei tule tai Kaisa ei tule:

$\neg J \lor \neg K$

Kolmannessa ehdossa on helppo erehtyä. ”Daniel tulee vain, jos myös Jari tulee” tarkoittaa, ettei saa käydä niin, että Daniel tulee ja Jari ei. Siis joko Daniel ei tule tai Jari tulee:

$\neg D \lor J$

Samalla tavalla kirjoitamme uudelleen loputkin. Koko tehtävä näyttää silloin tältä:

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

Katso, kuinka samanlaisia ehdot ovat: muutama kirjain, osassa merkki ¬, yhdistettyinä sanalla ”tai”. Eikä yhdessäkään ole enempää kuin kolme kirjainta. Tehtävää, jossa on tällaisia ehtoja ja jossa kirjaimille pitää antaa arvot tosi ja epätosi niin, että kaikki ehdot pätevät yhtä aikaa, kutsutaan nimellä 3-SAT. Kolmonen tarkoittaa, että ehdossa on enintään kolme kirjainta, ja SAT on lyhenne englannin sanasta satisfiability, toteutuvuus.

Ensi silmäyksellä se on pelkkä ajanvietepulma. Mutta valtava määrä käytännön tehtäviä voidaan kirjoittaa 3-SAT-muotoon: lukujärjestykset, sen tarkastaminen, että prosessorin piiri laskee oikein, vuorosuunnittelu ja myös sudokut. Silloin kirjaimia ei ole neljä, vaan vaikka miljoonia.

Montako vaihtoehtoa täytyy kokeilla?

Suoraviivaisin tapa on kokeilla kaikkea. Tomi tulee tai ei tule, se on kaksi vaihtoehtoa. Kummassakin Jari tulee tai ei tule, ja se on jo neljä vaihtoehtoa. Neljälle kaverille niitä on

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

Samoin päättelimme binäärivektoreiden kohdalla P vs. NP -artikkelissa. Jos kirjaimia on n, voimme antaa niille arvot tosi ja epätosi 2ⁿ tavalla. Neljälle kaverille se on 16 vaihtoehtoa, jotka käyt läpi muutamassa minuutissa. Sadalle kirjaimelle se on

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

vaihtoehtoa. Jos tietokone kokeilisi miljardi vaihtoehtoa sekunnissa, se tarvitsisi siihen noin kolmetuhatta kertaa niin paljon aikaa kuin maailmankaikkeus on ollut olemassa.

Toisin päin se on kuitenkin helppoa: jos joku sanoo ”kutsu nämä kolme”, tarkistat sen heti. Riittää käydä läpi kuusi ehtoa ja katsoa jokaisesta, päteekö se. Ratkaisun löytäminen on vaikeaa, sen tarkistaminen on helppoa. Juuri tällaiset tehtävät sijoitimme P vs. NP -artikkelissa luokkaan NP.

Mutta 3-SAT ei ole NP:ssä mikä tahansa tehtävä: vuonna 1971 osoitettiin, että jokainen NP:n tehtävä voidaan kääntää 3-SAT-tehtäväksi. Joka siis osaisi ratkaista 3-SAT:n nopeasti, osaisi ratkaista nopeasti kaiken, minkä voi tarkistaa nopeasti. Tehtäviä, joilla on tämä ominaisuus, kutsutaan NP-täydellisiksi, ja 3-SAT on niiden kuuluisin edustaja.

Onnistuuko se nopeammin kuin 2ⁿ?

Onnistuu. Aivan kaiken kokeileminen on tarpeetonta. Riittää esimerkiksi huomata, että Tomi ei tule: ensimmäisestä ehdosta seuraa silloin heti, että Kaisan on tultava. Kaikki vaihtoehdot, joissa kumpikaan ei tule, yliviivaamme saman tien. Fiksut algoritmit yhdistävät kokonaisen joukon tällaisia temppuja. Parhaat nykyisin tunnetut tarvitsevat noin

${1,307}^{n}$

askelta. Se on valtava hyppäys. Kun n = 100, luvun 10³⁰ sijasta tulee noin 4,2 · 10¹¹ askelta, minkä tietokone suorittaa muutamassa minuutissa.

Mutta varo, tässä on ansa. 1,307ⁿ on yhä eksponenttifunktio. Pienensimme kantalukua kahdesta lukuun 1,307, mutta muuttuja n on edelleen eksponentissa. Kun n kasvaa edelleen, se kaataa meidät lopulta silti. Kun n = 1000, jopa 1,307ⁿ on luku, jossa on 117 numeroa.

Entä miltä näyttäisi algoritmi, joka ei ole eksponentiaalinen? Esimerkiksi sellainen, joka tulee toimeen n³ askeleella. Se olisi polynomiaikainen, ja 3-SAT kuuluisi silloin luokkaan P. Polynomien ja eksponenttifunktioiden välissä on kuitenkin vielä harmaa alue: funktioita, jotka kasvavat nopeammin kuin mikään polynomi ja silti hitaammin kuin mikään eksponenttifunktio. Esimerkiksi

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

Tässä eksponentissa on vain luvun n neliöjuuri. Vertaillaan kaikkia neljää funktiota taulukossa:

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

Kun n = 1000, funktio $2^{\sqrt{n}}$ on samassa sarjassa kuin n³, kun taas molemmat eksponenttifunktiot ovat karanneet lukuihin, joille meillä ei ole edes nimiä. Funktioita kuten $2^{\sqrt{n}}$ , jotka kasvavat hitaammin kuin cⁿ millä tahansa ykköstä suuremmalla kantaluvulla c, kutsutaan alieksponentiaalisiksi.

Saman näyttää kuvaaja. Pystyakseli on logaritminen: jokainen pykälä ylöspäin tarkoittaa satatuhatta kertaa suurempaa lukua. Muuten kuvaan ei mahtuisi muuta kuin 2ⁿ.

$Funktioiden 2^n (punainen), 1{,}307^n (oranssi), 2^{\sqrt{n}} (sininen) ja n^3 (vihreä) kasvu logaritmisella pystyakselilla$

Eksponenttifunktiot ovat tällaisessa kuvaajassa suoria, jotka nousevat koko ajan. Punainen 2ⁿ on jyrkempi kuin oranssi 1,307ⁿ, mutta molemmat ovat suoria. Mielenkiintoista on, että oranssi on aluksi jopa vihreän n³:n alapuolella. Se ohittaa vihreän vasta noin kohdassa n = 42, mutta sitten lopullisesti. Sininen $2^{\sqrt{n}}$ sen sijaan taipuu ja pysyy alhaalla vihreän lähellä.

Mitä ETH tarkalleen väittää

Nyt voimme esittää hypoteesin. Vuonna 1999 sen muotoilivat Russell Impagliazzo ja Ramamohan Paturi:

On olemassa ykköstä suurempi luku c siten, että mikään algoritmi ei pysty ratkaisemaan n kirjaimen 3-SAT-tehtävää nopeammin kuin noin cⁿ askeleessa.

Entä selkokielellä? Eksponenttifunktion kantalukua osaamme pienentää fiksuilla tempuilla, kahdesta lukuun 1,5, lukuun 1,307, ehkä jonakin päivänä lukuun 1,2. Mutta emme koskaan paina sitä mielivaltaisen lähelle ykköstä. Jossain on raja, jonka alle ei päästä. Algoritmin, jonka kompleksisuus on $2^{\sqrt{n}}$ , ei siis ETH:n mukaan pitäisi olla olemassa.

Miksi hypoteesi? Koska kukaan ei osaa todistaa sitä. ETH on työoletus, aivan kuten P vs. NP -artikkelissa oletamme, että P ≠ NP. Useimmat tietojenkäsittelytieteilijät uskovat siihen, koska vuosikymmenten ponnistelut ovat tuottaneet vain sen, että kantaluku hiipii hitaasti kakkosesta alaspäin. Todistusta ei kuitenkaan ole kenelläkään kädessä.

ETH ja P vs. NP

Miten nämä kaksi kysymystä liittyvät toisiinsa? Kuvittele, että 3-SAT:lla on ”todellinen” vaikeusaste, nopein mahdollinen algoritmi. Se voi olla kolmella alueella:

3-SAT:n kolme vaikeusaluetta: polynomiaikainen (vihreä), alieksponentiaalinen (sininen) ja eksponentiaalinen (punainen)

Vihreä alue, polynomiaikainen. 3-SAT voidaan ratkaista esimerkiksi n³ askeleessa. Koska 3-SAT on NP-täydellinen, silloin pätisi P = NP, eikä ETH tietenkään pätisi.
Sininen alue, alieksponentiaalinen. 3-SAT voidaan ratkaista $2^{\sqrt{n}}$ askeleessa tai jossain sen kaltaisessa. Polynomiajassa ei, joten pätee P ≠ NP. Mutta ETH ei pätisi.
Punainen alue, eksponentiaalinen. Parempaan kuin cⁿ ei päästä. ETH pätee, ja sen myötä pätee myös P ≠ NP.

Kuvasta näkyy, että ETH on vahvempi väite kuin P ≠ NP. Se ei sano vain, ettei 3-SAT:ta voi ratkaista polynomiajassa, vaan ettei sitä voi ratkaista edes alieksponentiaalisessa ajassa. Joka todistaisi ETH:n, todistaisi sillä samalla myös P ≠ NP ja saisi miljoona dollaria.

Ja toisin päin: joka kumoaisi ETH:n, ei olisi sillä vielä todistanut, että P = NP. Hänelle riittää algoritmi sinisestä alueesta. Muista tämä, hyödynnämme sitä kohta.

Mihin ETH:ta tarvitaan

Sen todistaminen, ettei jokin tehtävä ratkea nopeasti, on tietojenkäsittelytieteessä uskomattoman vaikeaa. Lähes mitään sellaista emme osaa. ETH antaa meille takaoven: sen sijaan, että todistaisimme ”tehtävä X on vaikea”, todistamme ”tehtävä X on vaikea, jos ETH pätee”.

Miten? Osoitamme, että jos tehtävä X ratkeaisi nopeasti, myös 3-SAT ratkeaisi nopeasti. Otetaan esimerkiksi tämä: meillä on n ihmistä, ja joistakin pareista tiedämme, etteivät he siedä toisiaan. Haluamme jakaa heidät kolmeen huoneeseen niin, ettei yksikään tällainen pari joudu samaan huoneeseen. Tietojenkäsittelytieteilijät kutsuvat sitä graafin värittämiseksi kolmella värillä. Jokaisesta 3-SAT-tehtävästä sen voi muodostaa niin, että ihmisten määrä on vain muutamakertainen kirjainten määrään verrattuna. Jos ihmiset siis voitaisiin jakaa huoneisiin alieksponentiaalisessa ajassa, myös 3-SAT voitaisiin ratkaista alieksponentiaalisessa ajassa ja ETH kaatuisi.

Tällaisia ehdollisia tuloksia on nykyään satoja. Koko ala, joka tutkii, kuinka vaikeita yksittäiset tehtävät tarkalleen ovat, seisoo ETH:n varassa kuin talo perustuksillaan.

ETH:lla on myös vahvempi sisko, vahva eksponenttiaikahypoteesi (SETH). Se keskittyy tehtäviin, joissa ehdoissa saa olla enemmän kuin kolme kirjainta, vaikka kymmenen tai sata. SETH väittää, että mitä pidempiä ehtoja sallimme, sitä lähemmäs kakkosta paras mahdollinen kantaluku tulee. Pitkillä ehdoilla ei siis voisi säästää juuri mitään verrattuna tyhmään kaikkien 2ⁿ vaihtoehdon kokeilemiseen.

Miksi ETH:sta puhutaan nyt

Yhtiö OpenAI, jonka tunnet etenkin ChatGPT:n kautta, julkaisi lokakuussa 2026 esijulkaisun eli artikkelin, jota ei ole vielä vertaisarvioitu. Sen nimi on The Exponential Time Hypothesis is False, suomeksi ”Eksponenttiaikahypoteesi ei päde”. Siinä yhtiö väittää löytäneensä algoritmin, joka ratkaisee 3-SAT:n noin

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

askeleessa. Eksponentissa ei siis ole pelkkä n, vaan n jaettuna (luonnollisen) logaritmin neliöjuurella. Se nimittäjä kasvaa hirvittävän hitaasti, mutta se kasvaa, ja se riittää, jotta funktio on alieksponentiaalinen. Algoritmin kerrotaan jopa osaavan paitsi löytää yhden ratkaisun myös laskea, kuinka monta ratkaisua on olemassa.

Jos tämä pitäisi paikkansa, OpenAI:n algoritmi osuisi yllä olevan kuvan siniselle alueelle. Ja mitä se tarkoittaisi?

ETH kaatuisi ja sen mukana SETH sekä satoja ehdollisia tuloksia, jotka nojasivat niihin. Tietojenkäsittelytieteilijöiden täytyisi heittää pois tai kirjoittaa uusiksi runsaasti lauseita ”jos ETH pätee, niin …”.
P vs. NP -ongelmaa se ei ratkaisisi. Algoritmi ei edelleenkään ole polynomiaikainen.
Käytännössä lähes mikään ei muuttuisi. Kaavassa piilee vakioita, joita emme tunne. Jos ne olisivat yhtä suuria kuin yksi, $\sqrt{\ln n}$ olisi arvolla n = 1000 noin 2,6 ja saisimme noin 2³⁸⁰ askelta. Se on lähes sama kuin 1,307¹⁰⁰⁰ ≈ 2³⁸⁶ nykyisillä parhailla algoritmeilla. Uusi ohittaisi nykyiset algoritmit selvästi vasta vielä suuremmilla n:n arvoilla, ja kuinka paljon, riippuu juuri tuntemattomista vakioista. Sillä on siis lähinnä teoreettista merkitystä. Salaukseen ja pankkitoimintaan se ei vaikuta.

Toistaiseksi kyseessä on tarkistamaton väite. Todistus on pitkä ja tekninen, ja asiantuntijat ovat vasta alkaneet lukea sitä. Suuret ilmoitukset ratkaistuista ongelmista ovat aiemmin osoittautuneet monta kertaa virheellisiksi, joten tällä hetkellä pätee: odotamme, mitä asiantuntijat sanovat siitä. Tämän kappaleen kirjoitamme 27. lokakuuta 2026.

Juhlatehtävän ratkaisu

Sinun pitää kutsua Tomi, Jari ja Daniel, ei Kaisaa. Kuvassa on kaikki 16 vaihtoehtoa. Jokaisessa sarakkeessa on yksi vaihtoehto: täytetty ympyrä tarkoittaa, että kaveri tulee, tyhjä sitä, ettei hän tule. Punainen luku sarakkeen alla näyttää ensimmäisen ehdon, joka ei päde. Ainoa vaihtoehto, jossa kaikki ehdot pätevät, on kehystetty vihreällä.

Kaikki 16 vaihtoehtoa sille, keitä voi kutsua. Rivit vastaavat kavereita T, J, K, D, täytetty ympyrä tarkoittaa, että hän tulee.

Ja juuri tämä on se raaka voima, jota ETH pitää lähes voittamattomana: neljälle kaverille kuusitoista saraketta, sadalle kaverille enemmän sarakkeita kuin kehossamme on atomeja.

Katso myös

« Edellinen: Tietojenkäsittelytieteen suurin ongelma: P vs. NP

Seuraava: Trachtenbergin nopean yhteenlaskun menetelmä »