Hipoteza czasu wykładniczego (ETH)

Niektóre zadania umiemy rozwiązać tylko w taki sposób, że sprawdzamy prawie wszystkie możliwości. Hipoteza czasu wykładniczego, po angielsku Exponential Time Hypothesis, w skrócie ETH, to zakład informatyków, że w jednym konkretnym zadaniu inaczej się nie da, choćbyśmy byli nie wiadomo jak sprytni. Szybsze metody istnieją, ale nawet te najlepsze będą potrzebować liczby kroków, która wraz z rozmiarem zadania rośnie wykładniczo.

ETH jest ściśle związana z problemem P vs NP, któremu poświęciliśmy osobny artykuł. Jeśli go jeszcze nie czytałeś, zajrzyj tam najpierw, bo będziemy na nim budować. Przede wszystkim na tym, czym jest złożoność algorytmu i dlaczego między n² a 2ⁿ jest taka przepaść.

Kogo zaprosić na imprezę

Szykujesz imprezę i chcesz zaprosić czworo znajomych: Tomka, Janka, Kasię i Darka. Problem w tym, że między nimi panują różne relacje, a ty chcesz, żeby wszyscy byli zadowoleni. Po długim wypytywaniu wychodzi ci sześć warunków:

Przyjdzie Tomek lub Kasia (może nawet oboje).
Janek i Kasia nie znoszą się, więc nie przyjdą oboje.
Darek przyjdzie tylko wtedy, gdy przyjdzie też Janek.
Jeśli przyjdzie Tomek, musi przyjść też Kasia albo Darek.
Jeśli przyjdą Tomek i Kasia, musi przyjść też Janek.
Przyjdzie przynajmniej jeden z trójki Tomek, Janek, Darek.

Kogo zaprosić, żeby wszystkie warunki były spełnione naraz? Spróbuj wymyślić to sam, rozwiązanie chowamy na koniec artykułu.

Informatycy przepisaliby zadanie na język rachunku zdań. Każda osoba dostaje jedną literę, na przykład T jak Tomek. Litera jest albo prawdziwa (Tomek przyjdzie), albo fałszywa (Tomek nie przyjdzie). Symbol ∨ czytamy „lub”, a ¬ czytamy „nie”. Pierwszy warunek wygląda wtedy tak:

$T \lor K$

Drugi warunek mówi, że Janek nie przyjdzie lub Kasia nie przyjdzie:

$\neg J \lor \neg K$

Przy trzecim warunku łatwo się pomylić. „Darek przyjdzie tylko wtedy, gdy przyjdzie też Janek” znaczy, że nie może się zdarzyć, żeby Darek przyszedł, a Janek nie. Czyli albo Darek nie przyjdzie, albo przyjdzie Janek:

$\neg D \lor J$

W ten sam sposób przepisujemy resztę. Całe zadanie wygląda wtedy tak:

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

Zobacz, jak bardzo te warunki są do siebie podobne: kilka liter, niektóre ze znakiem ¬, połączonych słowem „lub”. I żaden z nich nie ma więcej niż trzy litery. Zadanie, w którym mamy takie warunki i szukamy sposobu, jak literom przypisać prawdę i fałsz, żeby wszystkie warunki były spełnione naraz, nazywa się 3-SAT. Trójka oznacza, że warunek ma co najwyżej trzy litery, a SAT to skrót od angielskiego satisfiability, czyli spełnialność.

Na pierwszy rzut oka to zabawa do kącika rozrywkowego. Tyle że do postaci 3-SAT da się przepisać ogromną liczbę praktycznych zadań: układanie planu lekcji, sprawdzanie, czy układ w procesorze liczy poprawnie, planowanie zmian w pracy, a także sudoku. Liter jest wtedy nie cztery, tylko spokojnie miliony.

Ile możliwości trzeba sprawdzić?

Najprostszy sposób to sprawdzić wszystko. Tomek przyjdzie albo nie przyjdzie, to dwie możliwości. Dla każdej z nich Janek przyjdzie albo nie, to już cztery możliwości. Dla czworga znajomych jest ich

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

Tak samo rozumowaliśmy przy wektorach binarnych w artykule o P vs NP. Jeśli mamy n liter, możemy przypisać im prawdę i fałsz na 2ⁿ sposobów. Dla 4 znajomych to 16 możliwości, które przejrzysz w kilka minut. Dla 100 liter to

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

możliwości. Gdyby komputer sprawdzał miliard możliwości na sekundę, potrzebowałby na to mniej więcej trzy tysiące razy więcej czasu, niż istnieje Wszechświat.

Ale w drugą stronę jest łatwo: gdy ktoś powie ci „zaproś tych trzech”, od razu to sprawdzisz. Wystarczy przejść przez sześć warunków i przy każdym zobaczyć, czy jest spełniony. Znaleźć rozwiązanie jest trudno, sprawdzić je jest łatwo. Właśnie takie zadania w artykule o P vs NP zaliczyliśmy do klasy NP.

Tyle że 3-SAT nie jest w NP zwykłym zadaniem: w 1971 roku wykazano, że do 3-SAT da się przetłumaczyć każde zadanie z NP. Kto więc umiałby szybko rozwiązywać 3-SAT, umiałby szybko rozwiązać absolutnie wszystko, co da się szybko sprawdzić. Zadania z tą własnością nazywamy NP-zupełnymi, a 3-SAT jest ich najsłynniejszym przedstawicielem.

Czy da się szybciej niż 2ⁿ?

Da się. Sprawdzanie absolutnie wszystkiego jest zbędne. Wystarczy na przykład zauważyć, że Tomek nie przyjdzie: z pierwszego warunku od razu wynika, że musi przyjść Kasia. Wszystkie możliwości, w których nie przyszłoby ani jedno z nich, od razu skreślamy. Sprytne algorytmy łączą całą masę takich sztuczek. Te najlepsze znane dziś potrzebują mniej więcej

${1,307}^{n}$

kroków. To ogromny skok. Dla n = 100 zamiast 10³⁰ wychodzi około 4,2 · 10¹¹ kroków, które komputer wykona w kilka minut.

Ale uwaga, podstęp. 1,307ⁿ to wciąż funkcja wykładnicza. Zmniejszyliśmy podstawę z dwójki na 1,307, ale zmienna n została w wykładniku. Gdy n będzie dalej rosnąć, i tak w końcu nas przygniecie. Dla n = 1000 nawet 1,307ⁿ to liczba o 117 cyfrach.

A jak wyglądałby algorytm, który wykładniczy nie jest? Na przykład taki, któremu wystarczy n³ kroków. Byłby wielomianowy, a 3-SAT należałby wtedy do klasy P. Między wielomianami a funkcjami wykładniczymi leży jednak jeszcze szara strefa: funkcje, które rosną szybciej niż każdy wielomian, a mimo to wolniej niż każda funkcja wykładnicza. Na przykład

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

Tu w wykładniku jest tylko pierwiastek z n. Porównajmy wszystkie cztery funkcje w tabeli:

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

Dla n = 1000 funkcja $2^{\sqrt{n}}$ jest w tej samej lidze co n³, podczas gdy obie funkcje wykładnicze uciekły w liczby, dla których nie mamy nawet nazw. Funkcje takie jak $2^{\sqrt{n}}$ , które rosną wolniej niż cⁿ dla dowolnej podstawy c większej od jedynki, nazywamy podwykładniczymi.

To samo widać na wykresie. Oś pionowa jest logarytmiczna: każda kreska w górę oznacza liczbę sto tysięcy razy większą. Inaczej na rysunku nie zmieściłoby się nic oprócz 2ⁿ.

$Wzrost funkcji 2^n (na czerwono), 1{,}307^n (na pomarańczowo), 2^{\sqrt{n}} (na niebiesko) i n^3 (na zielono) z logarytmiczną osią pionową$

Funkcje wykładnicze są na takim wykresie prostymi, które cały czas rosną. Czerwona 2ⁿ jest bardziej stroma niż pomarańczowa 1,307ⁿ, ale obie są prostymi. Ciekawe, że pomarańczowa na początku leży nawet pod zieloną n³. Wyprzedza ją dopiero około n = 42, ale potem już na zawsze. Niebieska $2^{\sqrt{n}}$ natomiast się wygina i trzyma się nisko przy zielonej.

Co dokładnie głosi ETH

Teraz możemy już sformułować hipotezę. W 1999 roku zrobili to Russell Impagliazzo i Ramamohan Paturi:

Istnieje liczba c większa od jedynki taka, że żaden algorytm nie umie rozwiązać 3-SAT z n literami szybciej niż mniej więcej w cⁿ kroków.

A po ludzku? Podstawę potęgi umiemy sprytnymi trikami zmniejszać, z dwójki do 1,5, do 1,307, może kiedyś do 1,2. Ale nigdy nie ściśniemy jej dowolnie blisko jedynki. Gdzieś jest granica, poniżej której się nie da. Algorytm o złożoności $2^{\sqrt{n}}$ nie powinien więc według ETH istnieć.

Dlaczego hipoteza? Bo nikt nie umie jej udowodnić. ETH to robocze założenie, podobnie jak w artykule o P vs NP zakładamy, że P ≠ NP. Większość informatyków w nią wierzy, bo dziesiątki lat starań przyniosły tylko tyle, że podstawa powoli zsuwa się z dwójki w dół. Dowodu jednak nikt nie ma w ręku.

ETH a P vs NP

Jak te dwa pytania się ze sobą wiążą? Wyobraź sobie, że 3-SAT ma jakąś „prawdziwą” trudność, czyli najszybszy możliwy algorytm. Może on leżeć w trzech pasmach:

Trzy pasma trudności 3-SAT: wielomianowe (na zielono), podwykładnicze (na niebiesko) i wykładnicze (na czerwono)

Zielone pasmo, wielomianowe. 3-SAT da się rozwiązać na przykład w n³ kroków. Ponieważ 3-SAT jest NP-zupełny, zachodziłoby wtedy P = NP, a ETH oczywiście by nie zachodziła.
Niebieskie pasmo, podwykładnicze. 3-SAT da się rozwiązać w $2^{\sqrt{n}}$ kroków albo w czymś podobnym. Wielomianowo nie, więc zachodzi P ≠ NP. Ale ETH by nie zachodziła.
Czerwone pasmo, wykładnicze. Lepiej niż cⁿ się nie da. ETH zachodzi, a w takim razie zachodzi też P ≠ NP.

Z rysunku widać, że ETH jest mocniejszym twierdzeniem niż P ≠ NP. Mówi nie tylko, że problemu 3-SAT nie da się rozwiązać wielomianowo, ale że nie da się go rozwiązać nawet podwykładniczo. Kto udowodniłby ETH, udowodniłby tym samym także P ≠ NP i dostałby milion dolarów.

A w drugą stronę: kto by ETH obalił, nie musiałby jeszcze udowodnić P = NP. Wystarczy mu algorytm z niebieskiego pasma. Zapamiętaj to, za chwilę z tego skorzystamy.

Do czego przydaje się ETH

Udowodnić, że jakiegoś zadania nie da się rozwiązać szybko, jest w informatyce niewiarygodnie trudno. Prawie nic takiego nie umiemy. ETH daje nam tylne drzwi: zamiast „zadanie X jest trudne” dowodzimy „zadanie X jest trudne, jeśli zachodzi ETH”.

Jak? Pokazujemy, że gdyby zadanie X dało się rozwiązać szybko, dałoby się szybko rozwiązać także 3-SAT. Weźmy na przykład takie: mamy n osób i o niektórych parach wiemy, że się nie znoszą. Chcemy rozdzielić je do trzech pokoi tak, żeby żadna taka para nie wylądowała w tym samym pokoju. Informatycy nazywają to kolorowaniem grafu trzema kolorami. Z każdego zadania 3-SAT da się je skonstruować tak, że liczba osób wychodzi tylko kilkukrotnością liczby liter. Gdyby więc osoby dało się rozdzielić do pokoi podwykładniczo, dałoby się podwykładniczo rozwiązywać także 3-SAT, a ETH by upadła.

Takich warunkowych wyników są dziś setki. Cała dziedzina, która bada, jak dokładnie trudne są poszczególne zadania, stoi na ETH jak dom na fundamentach.

ETH ma też mocniejszą siostrę, silną hipotezę czasu wykładniczego (SETH). Dotyczy ona zadań, w których warunki mogą mieć więcej niż trzy litery, na przykład dziesięć albo sto. SETH głosi, że im dłuższe warunki dopuścimy, tym bardziej najlepsza możliwa podstawa zbliża się do dwójki. Dla długich warunków nie dałoby się więc zaoszczędzić prawie nic w porównaniu z głupim sprawdzaniem wszystkich 2ⁿ możliwości.

Dlaczego o ETH jest teraz głośno

Firma OpenAI, którą znasz głównie dzięki ChatGPT, opublikowała w październiku 2026 preprint, czyli artykuł, który nie przeszedł jeszcze recenzji. Nosi tytuł The Exponential Time Hypothesis is False, po polsku „Hipoteza czasu wykładniczego jest fałszywa”. Firma twierdzi w nim, że znalazła algorytm, który rozwiązuje 3-SAT mniej więcej w

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

krokach. W wykładniku stoi więc nie samo n, tylko n podzielone przez pierwiastek z (naturalnego) logarytmu. Ten mianownik rośnie strasznie powoli, ale rośnie, i to wystarcza, żeby funkcja była podwykładnicza. Algorytm podobno umie nie tylko znaleźć jedno rozwiązanie, ale też policzyć, ile rozwiązań istnieje.

Gdyby to była prawda, algorytm od OpenAI wpadałby w niebieskie pasmo z rysunku wyżej. A co by to znaczyło?

ETH by upadła, a z nią także SETH i setki warunkowych wyników, które się na nich opierały. Informatycy musieliby mnóstwo „jeśli zachodzi ETH, to…” wyrzucić albo przepisać.
Problemu P vs NP by to nie rozwiązało. Algorytm wciąż nie jest wielomianowy.
W praktyce prawie nic by się nie zmieniło. We wzorze kryją się stałe, których nie znamy. Gdyby były równe jeden, dla n = 1000 wychodzi $\sqrt{\ln n}$ około 2,6 i dostalibyśmy mniej więcej 2³⁸⁰ kroków. To prawie tyle samo co 1,307¹⁰⁰⁰ ≈ 2³⁸⁶ u dzisiejszych najlepszych algorytmów. Dzisiejsze algorytmy nowy wyraźnie wyprzedziłby dopiero dla jeszcze większych n, a o ile, zależy właśnie od nieznanych stałych. Ma więc znaczenie głównie teoretyczne. Szyfrowania ani bankowości to nie dotyczy.

Na razie to niezweryfikowane twierdzenie. Dowód jest długi i techniczny, a eksperci dopiero zaczynają go czytać. Wielkie ogłoszenia o rozwiązanych problemach wielokrotnie okazywały się w przeszłości błędne, więc na razie obowiązuje: poczekamy, co powiedzą na to eksperci. Ten akapit piszemy 27 października 2026 roku.

Rozwiązanie zadania o imprezie

Zaprosić masz Tomka, Janka i Darka, Kasi nie. Na rysunku jest wszystkich 16 możliwości. W każdej kolumnie jest jedna możliwość: pełne kółko oznacza, że dana osoba przyjdzie, puste, że nie przyjdzie. Czerwona liczba pod kolumną pokazuje pierwszy warunek, który nie jest spełniony. Jedyna możliwość, przy której są spełnione wszystkie warunki, jest obramowana na zielono.

Wszystkie 16 możliwości, kogo zaprosić. Wiersze odpowiadają znajomym T, J, K, D, pełne kółko oznacza, że przyjdzie.

I to właśnie jest metoda siłowa, którą ETH uważa za prawie nie do pokonania: dla czworga znajomych szesnaście kolumn, dla stu znajomych więcej kolumn, niż jest atomów w naszym ciele.

Zobacz też

« Poprzedni: Problem milenijny: P vs NP

Dalszy: Metoda szybkiego dodawania Trachtenberga »