OpenAI i Anthropic opublikowały niezależnie dowody, że hipoteza czasu wykładniczego jest fałszywa.
ETH to 27‑letnie założenie w teoretycznej informatyce, zgodnie z którym niektórych problemów nie da się rozwiązać dużo szybciej niż metodą brute force. Teraz czołowe laboratoria AI mówią, że to po prostu nieprawda.
Jeśli dowody się obronią, będzie to jak dotąd najważniejszy wynik wygenerowany przez AI w informatyce. Wymusi też przewartościowanie dosłownie setek prac badawczych, które zakładały prawdziwość ETH.
W tym artykule wyjaśniamy, co właściwie oznacza hipoteza czasu wykładniczego oraz powiązane z nią P vs NP. Przyjrzymy się też, co dokładnie twierdzą oba zespoły, jak sprawdzano dowody i co zmienia się (a co nie) w kryptografii.
P vs NP po ludzku
P kontra NP pyta, czy każdy problem, którego rozwiązanie łatwo sprawdzić, jest też łatwy do znalezienia. To jeden z siedmiu Problemów Milenijnych i pozostaje otwarty mimo tych doniesień.
Klasyczną ilustracją jest Sudoku. Sprawdzenie wypełnionej planszy zajmuje sekundy: skanujesz każdy wiersz, kolumnę i blok w poszukiwaniu powtórek. Znalezienie rozwiązania z prawie pustej planszy może trwać znacznie dłużej, a różnica rośnie lawinowo wraz z rozmiarem.
- P to klasa problemów, które komputer potrafi rozwiązać w czasie wielomianowym, czyli nakład pracy rośnie jak n², n³ itd. wraz ze wzrostem rozmiaru wejścia n.
- NP to klasa problemów, dla których komputer potrafi zweryfikować proponowane rozwiązania w czasie wielomianowym.
Każdy problem z P jest też w NP. Otwarte pytanie brzmi, czy zachodzi odwrotność. Większość informatyków uważa, że P ≠ NP, więc niektóre problemy są z natury trudniejsze do rozwiązania niż do sprawdzenia. Współczesna kryptografia opiera się na tym przekonaniu: szyfrowanie jest łatwe, ale odszyfrowanie bez klucza powinno być trudne.
Czym jest hipoteza czasu wykładniczego?
ETH jest ostrzejsza: twierdzi, że jeden konkretny problem z NP, 3‑SAT, wymaga czasu wykładniczego bez względu na pomysłowość algorytmu. Zaproponowali ją pod koniec lat 90. Russell Impagliazzo i Ramamohan Paturi z UC San Diego, a do prac podstawowych przyczynił się Francis Zane.
Problem 3‑SAT
W 3‑SAT dostajesz formułę złożoną z n zmiennych prawda/fałsz i listy klauzul. Każda klauzula łączy trzy warunki spójnikiem OR, na przykład „x₁ jest prawdą LUB x₄ jest fałszem LUB x₇ jest prawdą”. Zadanie polega na znalezieniu wartości zmiennych, które jednocześnie spełniają wszystkie klauzule.
Brute force sprawdza wszystkie 2ⁿ ustawienia, więc każda dodatkowa zmienna podwaja pracę. Widać, że przy około 100 zmiennych to beznadziejne.
Co mówi ETH
ETH stwierdza, że istnieje stała c > 1 taka, że żaden algorytm nie rozwiąże 3‑SAT szybciej niż cⁿ. Sprytne algorytmy mogą zmniejszać podstawę poniżej 2, ale nigdy do czegoś podwykładniczego. Formalnie: istnieje δ > 0 takie, że 3‑SAT nie da się rozwiązać w czasie O(2δn).
Przez dekady postępy pasowały do tego obrazu. Naukowcy wciąż ścinali podstawę, ale pozostawała wyraźnie powyżej 1. Ponieważ 3‑SAT można przekształcić w wiele innych problemów, ETH stała się roboczym założeniem. Używano jej, by argumentować, że problemy takie jak Clique, Vertex Cover, Independent Set i inne też nie mogą być rozwiązywane dużo szybciej.
Jak wypada nowy wynik
| Podejście | Czas działania dla 3‑SAT | Rośnie wykładniczo? |
|---|
| Brute force | 2ⁿ | Tak |
| Najlepsze znane przed paź 2026 (deterministyczne) | około 1,328ⁿ | Tak |
| Najlepsze znane przed paź 2026 (randomizowane) | około 1,308ⁿ | Tak |
| OpenAI i Anthropic (paź 2026) | 2^O(n log log n / √log n) | Nie: podwykładniczy |
Nowe ograniczenie zapisuje się skrótowo jako 2o(n). Koszt na dodatkową zmienną zbliża się do 1 wraz ze wzrostem n, co jest dokładnie tym, co ETH uznawała za niemożliwe.
Co ogłosiły OpenAI i Anthropic
Oba laboratoria niezależnie osiągnęły zasadniczo to samo podwykładnicze ograniczenie i oba wsparły swoje prace dowodami sprawdzonymi maszynowo w asystencie dowodów Lean.
| | OpenAI | Anthropic |
|---|
| Artykuł | "The Exponential Time Hypothesis Is False" (67 stron) | "A 2o(n) Time Algorithm for 3-SAT" (49 stron) |
| Model | Nienazwany model wewnętrzny | Wewnętrzny model badawczy Claude, wymieniony jako autor |
| Odkrycie głównej idei | 16 października 2026 | 16 października 2026 |
| Upublicznienie | 26 października 2026 | 26–27 października 2026 |
| Weryfikacja | Dowód w Leanie nieco słabszego ograniczenia, które i tak obala ETH | Dowód w Lean 4 na bazie Mathlib, ponownie sprawdzony przez drugi kernel |
| Dodatkowe twierdzenia | Przyspieszenie nie rozciąga się na całe NP | Obala także silną ETH (SETH); nowa dolna granica dla obwodów |
Anthropic podaje, że Claude znalazł rdzeń algorytmu bez udziału człowieka po wygenerowaniu ok. 14 milionów tokenów. Metoda wykorzystuje sieci tensorowe i argumenty o rzędzie. Badacze potem pomogli w dopracowaniu finalnej publikacji.
Dlaczego oba laboratoria znalazły to tego samego dnia?
Żadne nie wyjaśniło zbieżności czasowej. Artykuł Anthropic nazywa wyniki niezależnymi i równoczesnymi, a oba opracowania idą innymi ścieżkami przez matematykę, by dojść do zasadniczo tej samej granicy.
Kontekst sprawia, że nakładanie się w czasie mniej zaskakuje. Oba zespoły kierują swoje modele na długie listy otwartych problemów, a OpenAI samo wypuściło setki artykułów matematycznych wygenerowanych przez AI na początku października. ETH to jeden z najlepiej znanych celów w dziedzinie, a oba modele uczyły się z tych samych publikacji. Niezależne, równoczesne odkrycia to też stary wzorzec w nauce, jak u Newtona i Leibniza w rachunku czy Darwina i Wallace’a w doborze naturalnym.
Na ile solidne są dowody?
Lean potwierdza, że formalne twierdzenie wynika logicznie z jego aksjomatów. Nie potwierdza jednak, że formalne twierdzenie mówi to samo co artykuł. Anthropic zauważa, że nikt maszynowo nie sprawdza tej zgodności, a OpenAI mówi, że jego plik Lean dowodzi nieco słabszej granicy niż ta w nagłówku.
Teraz ci sami badacze, którzy zaproponowali problem, Impagliazzo i Paturi, wraz z Ryanem Williamsem z MIT, organizują warsztaty, by ocenić, czy formalne sformułowania rzeczywiście uchwytują ETH. W ich liście podkreślono, że udział w przeglądzie nie oznacza poparcia. Na moment pisania artykułu nikt publicznie nie wskazał błędu.
Williams stwierdził, że części dowodu OpenAI wyglądają rutynowo, podczas gdy „dwie lub trzy obco wyglądające części” wciąż wymagają kontroli. Impagliazzo, jeden z autorów ETH, opisał wynik jako głęboko zaskakujący.
Co się zmienia, a co nie
W praktyce dziś nie zmienia się prawie nic (uff): nowe algorytmy pokonują brute force dopiero na wejściach znacznie większych niż cokolwiek, co komputer mógłby kiedykolwiek pomieścić.
Brak szybszych solverów SAT
Artykuł Anthropic mówi, że ich metoda pokonuje brute force tylko na astronomicznie dużych wejściach. Dla typowych formuł z pięcioma klauzulami na zmienną punkt przecięcia to liczba mająca około 10 000 cyfr. W najbardziej ogólnym przypadku to liczba o mniej więcej 100 milionach cyfr.
Autorzy dodają też, że ich podejście raczej nie pomoże poniżej ok. 10 milionów zmiennych. Solvery SAT używane w weryfikacji układów scalonych, harmonogramowaniu i planowaniu nie przyspieszą dzięki temu wynikowi.
Kryptografia nie jest złamana
Wynik nie dotyka P vs NP. Nikt tego nie sugeruje. OpenAI mówi, że sprawdziło, czy algorytm łamie realne systemy kryptograficzne, i jest raczej pewne, że nie.
Teoria do przepisania
Większy wpływ dotyczy badań. Rezultaty trudności oparte na ETH lub SETH wymagają teraz nowej podstawy, a niektórzy badacze mówią, że lata ich pracy mogą wymagać przeglądu. Nie wszystko jednak upada. Anthropic zaznacza, że wynik nie obala problemu wektorów ortogonalnych, który wspiera wiele wyników z fine‑grained complexity.
Dlaczego to ważne dla AI
Najważniejsze nie jest samo 3‑SAT, lecz to, kto znalazł odpowiedź: dwa systemy AI niezależnie obaliły hipotezę, której ludzcy eksperci ufali przez pokolenie.
AI jako współpracownik badawczy
Badacze opisują dziś nowe wyniki AI spadające co tydzień lub dwa, wywracające trwające projekty. Narzędzia formalne jak Lean stają się kluczowe, bo pozwalają ufać długiemu, maszynowo napisanemu dowodowi bez odtwarzania każdej linijki.
Ukryte skróty i samodoskonalenie
ETH utrwalała przekonanie, że niektóre problemy przeszukiwania nie mają sprytnego skrótu. Jeśli to przekonanie jest błędne, inne oczywiście trudne problemy też mogą skrywać skróty.
Myślę o odkrywaniu algorytmów jako obszarze, w którym takie skróty mogłyby bardzo się liczyć dla rekurencyjnego samodoskonalenia, czyli idei systemów AI, które pomagają projektować lepsze AI. Wykorzystanie AI do znajdowania szybszych algorytmów to jedna z konkretnych dróg, choć nic w tym wyniku nie robi tego bezpośrednio dziś.
Co to znaczy dla praktyków danych
Dla osób budujących rozwiązania z danymi wyróżniają się trzy lekcje:
- Teoria złożoności to nie tylko akademia: Wiedza, że problem jest NP‑trudny, podpowiada, kiedy myśleć o heurystykach, aproksymacjach lub solverach zamiast o dokładnym przeszukiwaniu.
- Weryfikacja to umiejętność: Wraz z tym, jak AI generuje coraz więcej kodu i analiz, sprawdzanie wyników (testami, dowodami czy replikowalnymi pipeline’ami) jest równie ważne jak ich produkcja.
- Asymptotyka może mylić: „Szybszy” algorytm w teorii może być bezużyteczny przy realnych rozmiarach.
Wnioski
Jeśli dowody przetrwają przegląd ekspertów, hipoteza czasu wykładniczego dołączy do krótkiej listy powszechnie wierzących przypuszczeń, które okazały się fałszywe (jak hipoteza Eulera o sumie potęg). Ale P vs NP pozostaje otwarte, a kryptografia na razie jest bezpieczna.
Kolejne kamienie milowe do obserwowania to warsztaty przeglądowe prowadzone przez autorów ETH, niezależne reimplementacje algorytmów oraz to, czy ktoś jeszcze ciaśniej zwiąże granicę.
Aby zbudować fundamenty stojące za takimi historiami, zobacz nasze kursy o strukturach danych i algorytmach, programowaniu w Pythonie i uczeniu maszynowym. Obejmują one myślenie w kategoriach wielkiego O, które sprawia, że takie wyniki są czytelne.
OpenAI i Anthropic opublikowały niezależnie dowody, że hipoteza czasu wykładniczego jest fałszywa.
ETH to 27‑letnie założenie w teoretycznej informatyce, zgodnie z którym niektórych problemów nie da się rozwiązać dużo szybciej niż metodą brute force. Teraz czołowe laboratoria AI mówią, że to po prostu nieprawda.
Jeśli dowody się obronią, będzie to jak dotąd najważniejszy wynik wygenerowany przez AI w informatyce. Wymusi też przewartościowanie dosłownie setek prac badawczych, które zakładały prawdziwość ETH.
W tym artykule wyjaśniamy, co właściwie oznacza hipoteza czasu wykładniczego oraz powiązane z nią P vs NP. Przyjrzymy się też, co dokładnie twierdzą oba zespoły, jak sprawdzano dowody i co zmienia się (a co nie) w kryptografii.
P vs NP po ludzku
P kontra NP pyta, czy każdy problem, którego rozwiązanie łatwo sprawdzić, jest też łatwy do znalezienia. To jeden z siedmiu Problemów Milenijnych i pozostaje otwarty mimo tych doniesień.
Klasyczną ilustracją jest Sudoku. Sprawdzenie wypełnionej planszy zajmuje sekundy: skanujesz każdy wiersz, kolumnę i blok w poszukiwaniu powtórek. Znalezienie rozwiązania z prawie pustej planszy może trwać znacznie dłużej, a różnica rośnie lawinowo wraz z rozmiarem.
Każdy problem z P jest też w NP. Otwarte pytanie brzmi, czy zachodzi odwrotność. Większość informatyków uważa, że P ≠ NP, więc niektóre problemy są z natury trudniejsze do rozwiązania niż do sprawdzenia. Współczesna kryptografia opiera się na tym przekonaniu: szyfrowanie jest łatwe, ale odszyfrowanie bez klucza powinno być trudne.
Czym jest hipoteza czasu wykładniczego?
ETH jest ostrzejsza: twierdzi, że jeden konkretny problem z NP, 3‑SAT, wymaga czasu wykładniczego bez względu na pomysłowość algorytmu. Zaproponowali ją pod koniec lat 90. Russell Impagliazzo i Ramamohan Paturi z UC San Diego, a do prac podstawowych przyczynił się Francis Zane.
Problem 3‑SAT
W 3‑SAT dostajesz formułę złożoną z n zmiennych prawda/fałsz i listy klauzul. Każda klauzula łączy trzy warunki spójnikiem OR, na przykład „x₁ jest prawdą LUB x₄ jest fałszem LUB x₇ jest prawdą”. Zadanie polega na znalezieniu wartości zmiennych, które jednocześnie spełniają wszystkie klauzule.
Brute force sprawdza wszystkie 2ⁿ ustawienia, więc każda dodatkowa zmienna podwaja pracę. Widać, że przy około 100 zmiennych to beznadziejne.
Co mówi ETH
ETH stwierdza, że istnieje stała c > 1 taka, że żaden algorytm nie rozwiąże 3‑SAT szybciej niż cⁿ. Sprytne algorytmy mogą zmniejszać podstawę poniżej 2, ale nigdy do czegoś podwykładniczego. Formalnie: istnieje δ > 0 takie, że 3‑SAT nie da się rozwiązać w czasie O(2δn).
Przez dekady postępy pasowały do tego obrazu. Naukowcy wciąż ścinali podstawę, ale pozostawała wyraźnie powyżej 1. Ponieważ 3‑SAT można przekształcić w wiele innych problemów, ETH stała się roboczym założeniem. Używano jej, by argumentować, że problemy takie jak Clique, Vertex Cover, Independent Set i inne też nie mogą być rozwiązywane dużo szybciej.
Jak wypada nowy wynik
Nowe ograniczenie zapisuje się skrótowo jako 2o(n). Koszt na dodatkową zmienną zbliża się do 1 wraz ze wzrostem n, co jest dokładnie tym, co ETH uznawała za niemożliwe.
Co ogłosiły OpenAI i Anthropic
Oba laboratoria niezależnie osiągnęły zasadniczo to samo podwykładnicze ograniczenie i oba wsparły swoje prace dowodami sprawdzonymi maszynowo w asystencie dowodów Lean.
Anthropic podaje, że Claude znalazł rdzeń algorytmu bez udziału człowieka po wygenerowaniu ok. 14 milionów tokenów. Metoda wykorzystuje sieci tensorowe i argumenty o rzędzie. Badacze potem pomogli w dopracowaniu finalnej publikacji.
Dlaczego oba laboratoria znalazły to tego samego dnia?
Żadne nie wyjaśniło zbieżności czasowej. Artykuł Anthropic nazywa wyniki niezależnymi i równoczesnymi, a oba opracowania idą innymi ścieżkami przez matematykę, by dojść do zasadniczo tej samej granicy.
Kontekst sprawia, że nakładanie się w czasie mniej zaskakuje. Oba zespoły kierują swoje modele na długie listy otwartych problemów, a OpenAI samo wypuściło setki artykułów matematycznych wygenerowanych przez AI na początku października. ETH to jeden z najlepiej znanych celów w dziedzinie, a oba modele uczyły się z tych samych publikacji. Niezależne, równoczesne odkrycia to też stary wzorzec w nauce, jak u Newtona i Leibniza w rachunku czy Darwina i Wallace’a w doborze naturalnym.
Na ile solidne są dowody?
Lean potwierdza, że formalne twierdzenie wynika logicznie z jego aksjomatów. Nie potwierdza jednak, że formalne twierdzenie mówi to samo co artykuł. Anthropic zauważa, że nikt maszynowo nie sprawdza tej zgodności, a OpenAI mówi, że jego plik Lean dowodzi nieco słabszej granicy niż ta w nagłówku.
Teraz ci sami badacze, którzy zaproponowali problem, Impagliazzo i Paturi, wraz z Ryanem Williamsem z MIT, organizują warsztaty, by ocenić, czy formalne sformułowania rzeczywiście uchwytują ETH. W ich liście podkreślono, że udział w przeglądzie nie oznacza poparcia. Na moment pisania artykułu nikt publicznie nie wskazał błędu.
Williams stwierdził, że części dowodu OpenAI wyglądają rutynowo, podczas gdy „dwie lub trzy obco wyglądające części” wciąż wymagają kontroli. Impagliazzo, jeden z autorów ETH, opisał wynik jako głęboko zaskakujący.
Co się zmienia, a co nie
W praktyce dziś nie zmienia się prawie nic (uff): nowe algorytmy pokonują brute force dopiero na wejściach znacznie większych niż cokolwiek, co komputer mógłby kiedykolwiek pomieścić.
Brak szybszych solverów SAT
Artykuł Anthropic mówi, że ich metoda pokonuje brute force tylko na astronomicznie dużych wejściach. Dla typowych formuł z pięcioma klauzulami na zmienną punkt przecięcia to liczba mająca około 10 000 cyfr. W najbardziej ogólnym przypadku to liczba o mniej więcej 100 milionach cyfr.
Autorzy dodają też, że ich podejście raczej nie pomoże poniżej ok. 10 milionów zmiennych. Solvery SAT używane w weryfikacji układów scalonych, harmonogramowaniu i planowaniu nie przyspieszą dzięki temu wynikowi.
Kryptografia nie jest złamana
Wynik nie dotyka P vs NP. Nikt tego nie sugeruje. OpenAI mówi, że sprawdziło, czy algorytm łamie realne systemy kryptograficzne, i jest raczej pewne, że nie.
Teoria do przepisania
Większy wpływ dotyczy badań. Rezultaty trudności oparte na ETH lub SETH wymagają teraz nowej podstawy, a niektórzy badacze mówią, że lata ich pracy mogą wymagać przeglądu. Nie wszystko jednak upada. Anthropic zaznacza, że wynik nie obala problemu wektorów ortogonalnych, który wspiera wiele wyników z fine‑grained complexity.
Dlaczego to ważne dla AI
Najważniejsze nie jest samo 3‑SAT, lecz to, kto znalazł odpowiedź: dwa systemy AI niezależnie obaliły hipotezę, której ludzcy eksperci ufali przez pokolenie.
AI jako współpracownik badawczy
Badacze opisują dziś nowe wyniki AI spadające co tydzień lub dwa, wywracające trwające projekty. Narzędzia formalne jak Lean stają się kluczowe, bo pozwalają ufać długiemu, maszynowo napisanemu dowodowi bez odtwarzania każdej linijki.
Ukryte skróty i samodoskonalenie
ETH utrwalała przekonanie, że niektóre problemy przeszukiwania nie mają sprytnego skrótu. Jeśli to przekonanie jest błędne, inne oczywiście trudne problemy też mogą skrywać skróty.
Myślę o odkrywaniu algorytmów jako obszarze, w którym takie skróty mogłyby bardzo się liczyć dla rekurencyjnego samodoskonalenia, czyli idei systemów AI, które pomagają projektować lepsze AI. Wykorzystanie AI do znajdowania szybszych algorytmów to jedna z konkretnych dróg, choć nic w tym wyniku nie robi tego bezpośrednio dziś.
Co to znaczy dla praktyków danych
Dla osób budujących rozwiązania z danymi wyróżniają się trzy lekcje:
Wnioski
Jeśli dowody przetrwają przegląd ekspertów, hipoteza czasu wykładniczego dołączy do krótkiej listy powszechnie wierzących przypuszczeń, które okazały się fałszywe (jak hipoteza Eulera o sumie potęg). Ale P vs NP pozostaje otwarte, a kryptografia na razie jest bezpieczna.
Kolejne kamienie milowe do obserwowania to warsztaty przeglądowe prowadzone przez autorów ETH, niezależne reimplementacje algorytmów oraz to, czy ktoś jeszcze ciaśniej zwiąże granicę.
Aby zbudować fundamenty stojące za takimi historiami, zobacz nasze kursy o strukturach danych i algorytmach, programowaniu w Pythonie i uczeniu maszynowym. Obejmują one myślenie w kategoriach wielkiego O, które sprawia, że takie wyniki są czytelne.