Ipoteza timpului exponențial (ETH)

Unele probleme știm să le rezolvăm doar încercând aproape toate posibilitățile. Ipoteza timpului exponențial, în engleză Exponential Time Hypothesis și pe scurt ETH, este pariul informaticienilor că, pentru o anumită problemă, nu se poate altfel, oricât de inteligenți am fi. Metode mai rapide există, dar chiar și cele mai bune vor avea nevoie de un număr de pași care crește exponențial cu mărimea problemei.

ETH este strâns legată de problema P versus NP, căreia i-am dedicat un articol separat. Dacă nu l-ai citit încă, uită-te mai întâi acolo, pentru că ne vom sprijini pe el. Mai ales pe ce este complexitatea unui algoritm și de ce între n² și 2ⁿ este o prăpastie atât de mare.

Pe cine invităm la petrecere

Pregătești o petrecere și vrei să inviți patru prieteni: pe Tudor, Julian, Karina și Dan. Necazul este că între ei există tot felul de relații, iar tu vrei ca toți să fie mulțumiți. După multe întrebări ajungi la șase condiții:

1. Vine Tudor sau Karina (poate chiar amândoi).
2. Julian și Karina nu se suportă, așa că nu vor veni amândoi.
3. Dan vine doar dacă vine și Julian.
4. Dacă vine Tudor, trebuie să vină și Karina sau Dan.
5. Dacă vin și Tudor, și Karina, trebuie să vină și Julian.
6. Vine cel puțin unul din trio-ul Tudor, Julian, Dan.

Pe cine să inviți, ca toate condițiile să fie îndeplinite deodată? Încearcă să te gândești singur, soluția o ascundem la sfârșitul articolului.

Informaticienii ar rescrie problema în limbajul logicii propoziționale. Fiecare prieten primește o literă, de exemplu T ca Tudor. Litera este fie adevărată (Tudor vine), fie falsă (Tudor nu vine). Simbolul ∨ îl citim „sau”, iar ¬ îl citim „non”. Prima condiție arată atunci așa:

$$T\vee K$$

A doua condiție spune că Julian nu vine sau Karina nu vine:

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

La a treia condiție este ușor să te încurci. „Dan vine doar dacă vine și Julian” înseamnă că nu se poate întâmpla ca Dan să vină, iar Julian nu. Deci fie Dan nu vine, fie vine Julian:

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

La fel rescriem restul. Toată problema arată atunci așa:

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

Vezi cât de asemănătoare sunt condițiile: câteva litere, unele cu semnul ¬, legate prin cuvântul „sau”. Și niciuna nu are mai mult de trei litere. Problema în care avem astfel de condiții și căutăm cum să atribuim literelor adevărul și falsul, astfel încât toate condițiile să fie îndeplinite deodată, se numește 3-SAT. Trei înseamnă că o condiție are cel mult trei litere, iar SAT este prescurtarea englezescului satisfiability, adică satisfiabilitate.

La prima vedere este un joc pentru rubrica de divertisment. Numai că sub forma 3-SAT se poate rescrie un număr uriaș de probleme practice: orare, verificarea faptului că un cip dintr-un procesor calculează corect, planificarea turelor și chiar sudoku. Literele nu mai sunt atunci patru, ci lejer milioane.

Câte posibilități trebuie încercate?

Cea mai directă cale este să încercăm tot. Tudor vine sau nu vine, sunt două posibilități. Pentru fiecare dintre ele, Julian vine sau nu, sunt deja patru posibilități. Pentru patru prieteni sunt

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

Așa am raționat și la vectorii binari din articolul despre P versus NP. Dacă avem n litere, le putem atribui adevărul și falsul în 2ⁿ moduri. Pentru 4 prieteni sunt 16 posibilități, pe care le parcurgi în câteva minute. Pentru 100 de litere sunt

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

posibilități. Dacă un calculator ar încerca un miliard de posibilități pe secundă, ar avea nevoie de aproximativ trei mii de ori mai mult timp decât există Universul.

În sens invers, însă, e simplu: când cineva îți spune „invită-i pe acești trei”, verifici imediat. E de ajuns să parcurgi cele șase condiții și să te uiți la fiecare dacă e îndeplinită. A găsi soluția este greu, a o verifica este ușor. Exact astfel de probleme le-am încadrat în articolul despre P versus NP în clasa NP.

Numai că 3-SAT nu este în NP o problemă oarecare: în 1971 s-a arătat că la 3-SAT se poate reduce orice problemă din NP. Cine ar rezolva rapid 3-SAT ar rezolva rapid absolut tot ce se poate verifica rapid. Problemele cu această proprietate se numesc NP-complete, iar 3-SAT este cea mai faimoasă reprezentantă a lor.

Se poate mai repede decât 2ⁿ?

Se poate. Să încercăm absolut tot este de prisos. E de ajuns, de exemplu, să observăm că Tudor nu vine: din prima condiție rezultă atunci imediat că trebuie să vină Karina. Toate posibilitățile în care n-ar veni niciunul dintre ei le tăiem direct. Algoritmii isteți combină o mulțime de asemenea trucuri. Cei mai buni cunoscuți astăzi au nevoie de aproximativ

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

pași. E un salt uriaș. Pentru n = 100, în loc de 10³⁰ ies aproximativ 4,2 · 10¹¹ pași, pe care calculatorul îi face în câteva minute.

Dar atenție, e o capcană. 1,307ⁿ este tot o funcție exponențială. Am micșorat baza de la doi la 1,307, dar variabila n a rămas în exponent. Când n va crește în continuare, ne va strivi oricum până la urmă. Pentru n = 1000 chiar și 1,307ⁿ este un număr cu 117 cifre.

Și cum ar arăta un algoritm care nu este exponențial? De exemplu unul căruia îi ajung n³ pași. Ar fi polinomial, iar 3-SAT ar aparține atunci clasei P. Între polinoame și exponențiale mai există însă o zonă gri: funcții care cresc mai repede decât orice polinom și totuși mai încet decât orice exponențială. De exemplu

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

Aici în exponent este doar rădăcina pătrată din n. Să comparăm toate cele patru funcții într-un tabel:

Pentru n = 1000, $2^{\sqrt{n}}$ este în aceeași categorie cu n³, în timp ce ambele exponențiale au fugit spre numere pentru care nu avem nici măcar nume. Funcțiile precum $2^{\sqrt{n}}$, care cresc mai încet decât cⁿ pentru orice bază c mai mare decât unu, se numesc subexponențiale.

Același lucru îl arată graficul. Axa verticală este logaritmică: fiecare gradație în sus înseamnă un număr de o sută de mii de ori mai mare. Altfel, în figură n-ar încăpea nimic în afară de 2ⁿ.

Funcțiile exponențiale sunt într-un asemenea grafic drepte care urcă mereu. Cea roșie, 2ⁿ, este mai abruptă decât cea portocalie, 1,307ⁿ, dar amândouă sunt drepte. Interesant este că cea portocalie se află la început chiar sub cea verde, n³. O depășește abia pe la n = 42, dar apoi pentru totdeauna. Cea albastră, $2^{\sqrt{n}}$, în schimb, se curbează și rămâne jos, lângă cea verde.

Ce afirmă exact ETH

Acum putem formula ipoteza. În 1999 au formulat-o Russell Impagliazzo și Ramamohan Paturi:

Există un număr c mai mare decât unu astfel încât niciun algoritm nu poate rezolva 3-SAT cu n litere mai repede decât în aproximativ cⁿ pași.

Iar pe românește? Baza exponențialei știm s-o micșorăm cu trucuri istețe, de la doi la 1,5, la 1,307, poate cândva la 1,2. Dar nu o vom strânge niciodată oricât de aproape de unu. Undeva există o limită sub care nu se poate. Un algoritm cu complexitatea $2^{\sqrt{n}}$ n-ar trebui deci, după ETH, să existe.

De ce ipoteză? Pentru că nimeni nu știe s-o demonstreze. ETH este o presupunere de lucru, la fel cum în articolul despre P versus NP presupunem că P ≠ NP. Majoritatea informaticienilor o cred, pentru că zeci de ani de eforturi au adus doar faptul că baza alunecă încet de la doi în jos. Demonstrația însă n-o are nimeni în mână.

ETH și P versus NP

Cum se leagă cele două întrebări? Imaginează-ți că 3-SAT are o dificultate „adevărată”, cel mai rapid algoritm posibil. Acesta se poate afla în trei benzi:

• Banda verde, polinomială. 3-SAT se poate rezolva, să zicem, în n³ pași. Fiindcă 3-SAT este NP-completă, ar fi atunci P = NP, iar ETH desigur n-ar fi adevărată.
• Banda albastră, subexponențială. 3-SAT se poate rezolva în $2^{\sqrt{n}}$ pași sau ceva asemănător. Polinomial nu, deci este adevărat P ≠ NP. Dar ETH n-ar fi adevărată.
• Banda roșie, exponențială. Mai bine de cⁿ nu se poate. ETH este adevărată și, prin urmare, este adevărat și P ≠ NP.

Din figură se vede că ETH este o afirmație mai tare decât P ≠ NP. Ea spune nu doar că 3-SAT nu se rezolvă polinomial, ci că nu se rezolvă nici subexponențial. Cine ar demonstra ETH ar demonstra prin asta și P ≠ NP și ar primi un milion de dolari.

Și invers: cine ar infirma ETH n-ar fi demonstrat neapărat prin asta P = NP. Îi ajunge un algoritm din banda albastră. Ține minte asta, în curând o să ne fie de folos.

La ce e bună ETH

A demonstra că o problemă nu se poate rezolva rapid este în informatică incredibil de greu. Aproape nimic de felul acesta nu știm să facem. ETH ne dă o ușă din spate: în loc de „problema X este grea” demonstrăm „problema X este grea, dacă este adevărată ETH”.

Cum? Arătăm că, dacă problema X s-ar putea rezolva rapid, s-ar putea rezolva rapid și 3-SAT. Să luăm de exemplu următoarea: avem n oameni și despre unele perechi știm că nu se suportă. Vrem să-i împărțim în trei camere astfel încât nicio astfel de pereche să nu ajungă în aceeași cameră. Informaticienii o numesc colorarea unui graf cu trei culori. Din orice problemă 3-SAT se poate construi o asemenea problemă, astfel încât numărul de oameni să iasă doar de câteva ori mai mare decât numărul de litere. Deci dacă oamenii s-ar putea împărți în camere subexponențial, s-ar rezolva subexponențial și 3-SAT, iar ETH ar cădea.

Astăzi există sute de asemenea rezultate condiționate. Întregul domeniu care studiază cât de grele sunt exact diversele probleme stă pe ETH ca o casă pe fundație.

ETH are și o soră mai puternică, ipoteza tare a timpului exponențial (SETH). Ea se referă la probleme în care condițiile pot avea mai mult de trei litere, de exemplu zece sau o sută. SETH afirmă că, cu cât permitem condiții mai lungi, cu atât mai mult se apropie cea mai bună bază posibilă de doi. Pentru condiții lungi nu s-ar putea deci economisi aproape nimic față de încercarea proastă a tuturor celor 2ⁿ posibilități.

De ce se vorbește acum despre ETH

Compania OpenAI, pe care o știi mai ales datorită ChatGPT, a publicat în octombrie 2026 un preprint, adică un articol care nu a trecut încă prin recenzie. Se numește The Exponential Time Hypothesis is False, în română „Ipoteza timpului exponențial este falsă”. Compania afirmă în el că a găsit un algoritm care rezolvă 3-SAT în aproximativ

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

pași. În exponent nu stă deci doar n, ci n împărțit la rădăcina pătrată din logaritmul (natural). Acest numitor crește îngrozitor de încet, dar crește, și asta ajunge ca funcția să fie subexponențială. Algoritmul ar putea, chipurile, nu doar să găsească o soluție, ci și să numere câte soluții există.

Dacă ar fi așa, algoritmul de la OpenAI ar cădea în banda albastră din figura de mai sus. Și ce ar însemna asta?

• ETH ar cădea și odată cu ea SETH și sutele de rezultate condiționate care stăteau pe ele. Informaticienii ar trebui să arunce sau să rescrie o mulțime de „dacă este adevărată ETH, atunci…”.
• Problema P versus NP nu ar fi astfel rezolvată. Algoritmul tot nu este polinomial.
• În practică aproape nimic nu s-ar schimba. În formulă se ascund constante pe care nu le cunoaștem. Dacă ar fi egale cu unu, pentru n = 1000 iese $\sqrt{\ln n}$ aproximativ 2,6 și am obține aproximativ 2³⁸⁰ pași. Este aproape la fel cu 1,307¹⁰⁰⁰ ≈ 2³⁸⁶ la cei mai buni algoritmi de azi. Cel nou i-ar depăși clar pe algoritmii de azi abia pentru n și mai mari, iar cu cât anume depinde tocmai de constantele necunoscute. Are deci mai ales importanță teoretică. Criptarea sau sistemul bancar nu sunt afectate.

Deocamdată este o afirmație neverificată. Demonstrația este lungă și tehnică, iar specialiștii abia încep s-o citească. Anunțurile mari despre probleme rezolvate s-au dovedit în trecut de multe ori greșite, așa că deocamdată rămâne valabil: așteptăm să vedem ce vor spune specialiștii. Acest paragraf îl scriem pe 27 octombrie 2026.

Soluția problemei cu petrecerea

Trebuie să-i inviți pe Tudor, Julian și Dan, pe Karina nu. În figură sunt toate cele 16 posibilități. În fiecare coloană este o posibilitate: cercul plin înseamnă că prietenul vine, cel gol că nu vine. Numărul roșu de sub coloană arată prima condiție care nu este îndeplinită. Singura posibilitate la care sunt îndeplinite toate condițiile este încadrată cu verde.

Și exact aceasta este forța brută pe care ETH o consideră aproape de neînvins: pentru patru prieteni șaisprezece coloane, pentru o sută de prieteni mai multe coloane decât sunt atomi în corpul nostru.

Vezi și

• Cea mai mare problemă din informatică: P versus NP
• Logica propozițională
• Funcția exponențială
• Creșterea exponențială