OpenAI ogłosiło obalenie ETH. Dlaczego świat algorytmów czeka na weryfikację?
By Paweł Lisowski
Spis treści
OpenAI ogłosiło, że jego model znalazł i sformalizował dowód obalenia hipotezy czasu wykładniczego (ETH). To ważna deklaracja dla informatyki teoretycznej, ale nie oznacza jeszcze rozwiązania problemu P kontra NP ani natychmiastowego przełomu w szyfrowaniu. Wynik ma teraz przejść otwartą analizę specjalistów.
Według oficjalnego komunikatu OpenAI chodzi o hipotezę dotyczącą problemu spełnialności formuł logicznych. Firma twierdzi, że model znalazł algorytm działający w czasie podwykładniczym, a następnie wynik został sformalizowany w systemie Lean.
ETH w prostych słowach
Hipoteza czasu wykładniczego mówi, w uproszczeniu, że nie istnieje algorytm rozwiązujący problem 3-SAT w czasie 2o(n). 3-SAT polega na sprawdzeniu, czy da się tak ustawić wartości logiczne zmiennych, aby spełnić jednocześnie zestaw klauzul. Liczba ustawień rośnie bardzo szybko, dlatego poprawa algorytmu może mieć znaczenie dla wielu innych problemów.
ETH jest mocniejszym założeniem niż samo przypuszczenie, że P różni się od NP. Jeśli ETH jest prawdziwa, wynika z niej między innymi P ≠ NP. Jeśli jednak ETH okaże się fałszywa, nie wynika z tego automatycznie, że wszystkie problemy, których rozwiązania łatwo zweryfikować, da się także szybko rozwiązywać. Clay Mathematics Institute nadal opisuje P kontra NP jako nierozwiązany problem milenijny.
Co może się zmienić?
ETH jest używana jako punkt odniesienia w pracach o algorytmach grafowych, bazach danych, geometrii obliczeniowej i biologii obliczeniowej. Jeżeli argument OpenAI się utrzyma, część wyników warunkowych będzie wymagała ponownego sprawdzenia. Klasyczna praca Impagliazza, Paturiego i Zane’a pokazuje, jak szeroko takie zależności mogą sięgać.
Nie należy mylić teoretycznej granicy z wydajnością dzisiejszych programów. Algorytm może mieć lepszą klasę złożoności, a mimo to być zbyt kosztowny dla praktycznych danych. Nie wynika też z tego, że złamano współczesne systemy kryptograficzne.
Dlaczego potrzebna jest niezależna kontrola?
Weryfikację ma prowadzić grupa kierowana przez Russella Impagliazza, Ramamohana Paturiego i Ryana Williamsa. Formalizacja w Lean sprawdza zgodność dowodu z regułami systemu, ale nie zastępuje oceny założeń i tego, czy formalizowany wynik odpowiada standardowej wersji ETH.
Najuczciwszy opis sytuacji brzmi więc: OpenAI przedstawiło potencjalnie przełomową refutację, a nie powszechnie zaakceptowane rozstrzygnięcie. Konsekwencje będą znane dopiero po pracy niezależnych badaczy.
Źródła
Autor Artykułu
Paweł Lisowski
Paweł Lisowski - pasjonat technologii, komputerów i internetu. Od wielu lat śledzi rozwój sprzętu i oprogramowania, testuje nowe rozwiązania i dzieli się wiedzą z czytelnikami. Zafascynowany wpływem technologii na codzienne życie, tworzy praktyczne poradniki i inspiruje do świadomego korzystania z cyfrowego świata.