26 października 2026 r. OpenAI ogłosiła, że jej wewnętrzny system uzyskał wynik, który według firmy obala Exponential Time Hypothesis (ETH), hipotezę zakładającą wykładniczy czas działania dla 3-SAT w najgorszym przypadku. OpenAI datuje otrzymanie wyniku w języku naturalnym na 16 października, a jego formalizację w systemie Lean na 17 października.
Co OpenAI ogłosiła o ETH
OpenAI opublikowała manuskrypt i dokumentację Lean oraz zapowiedziała zewnętrzną analizę wyniku. Grupę, która ma go sprawdzić i objaśnić, współprowadzą Russell Impagliazzo, Ramamohan Paturi i Ryan Williams. Samo ogłoszenie firmy przedstawia wynik jako jej twierdzenie, a nie niezależny werdykt naukowy.
Co formalizuje Lean
Publiczna dokumentacja Lean opisuje twierdzenie o deterministycznym, dokładnym zliczaniu przypisań spełniających kanonicznie zakodowaną formułę k-CNF dla ustalonego k ≥ 2. Dokładne zliczanie oznacza tu policzenie wszystkich przypisań zmiennych, które spełniają formułę, a nie tylko rozstrzygnięcie, czy istnieje choć jedno takie przypisanie.
Dla n zmiennych i wejścia o długości kodowania L podana granica czasu to (L+1)^{O_k(1)} 2^{O_k(n(log log n)^2/√log n)}. Dokumentacja podaje też, że maszyna odwiedza łącznie najwyżej (L+1)^{O_k(1)} komórek taśmy. Indeks k przy O_k oznacza, że stałe w oszacowaniu mogą zależeć od ustalonego k.
Ostrzejsze granice przypisane manuskryptowi
Dokumentacja zakresu Lean odróżnia sformalizowaną granicę czasu od ostrzejszej granicy, którą przypisuje manuskryptowi z 25 października: (n+m)^{O_k(1)} 2^{O_k(n log log n/√log n)}, gdzie m oznacza liczbę klauzul. To osobne oszacowanie, a nie granica podana dla twierdzenia sformalizowanego w Lean.
Dla przypadku, w którym liczba klauzul spełnia warunek m ≤ Dn przy ustalonym D > 0, dokumentacja przypisuje manuskryptowi jeszcze granicę (n+m)^{O_{k,D}(1)} 2^{O_{k,D}(n/√log n)}. Ten warunek oznacza, że liczba klauzul jest ograniczona przez stałą wielokrotność liczby zmiennych.
Oficjalna dokumentacja Lean opisuje zakres twierdzenia i osobno przytacza granice manuskryptu.
Co te granice mówią o praktyce
ETH jest wykorzystywana w setkach prac do wyprowadzania warunkowych wyników o trudności problemów między innymi z teorii grafów, biologii obliczeniowej, baz danych i geometrii obliczeniowej. OpenAI wiąże ją z problemem P kontra NP, ale ogłoszony wynik dotyczy złożoności problemów spełnialności i nie rozstrzyga P kontra NP.
Granica asymptotyczna opisuje zachowanie algorytmu wraz ze wzrostem rozmiaru wejścia. Sama w sobie nie oznacza natychmiastowego przyspieszenia programów ani solverów SAT. OpenAI zaznacza, że przełożenie postępów teoretycznych na praktyczne ulepszenia wymaga znaczących dalszych badań. W relacji z 28 października 2026 r. ExplainX podał, że do tej daty nie zgłoszono niezależnego potwierdzenia wyniku.
