OpenAI twierdzi, że model sztucznej inteligencji znalazł sposób na obalenie hipotezy czasu wykładniczego (ETH) – hipotezy z zakresu informatyki postawionej w 1999 roku. To twierdzenie nie ma nic wspólnego z Ethereum, kryptowalutą notowaną pod tickerem ETH, ani ze współzałożycielem Ethereum Vitalikiem Buterinem.

Pomimo tego ogłoszenie wywołało żarty na Crypto Twitter. „Damn algo traders just slaughtered $ETH” – napisał na X użytkownik Takumi, a Andrew Jiang dodał: „Vitalik has been real quiet since this came out.”

Chodzi o hipotezę ETH zaproponowaną przez informatyków Russella Impagliazzo, Ramamohana Paturiego i Francisa Zane'a. Głosi ona, że problem logiczny znany jako 3-SAT nie może zostać rozwiązany znacząco szybciej niż poprzez zbadanie wszystkich możliwych kombinacji zmiennych. W 3-SAT celem jest ustalenie, czy przypisania wartości prawda–fałsz mogą spełnić zbiór reguł, przy czym każda reguła zawiera trzy zmienne.

Setki prac naukowych opierało się na tej hipotezie, aby wykazać, że niektóre problemy z teorii grafów, biologii obliczeniowej, baz danych i geometrii nie mogą być szybko rozwiązane – według OpenAI. Firma stwierdziła, że obalenie ETH może na nowo otworzyć pytania o to, jak dużo szybciej te zadania mogłyby być rozwiązywane, i pomóc badaczom w poszukiwaniu ulepszonych algorytmów.

„Obalenie ETH otwiera na nowo pytania o to, jak bardzo szybsze mogłyby stać się te zadania – napisała firma w wpisie na blogu – i może pomóc ukierunkować poszukiwanie lepszych algorytmów.”

Liczący 67 stron artykuł OpenAI, opatrzony datą 17 października i zrewidowany 25 października, opisuje algorytm deterministyczny – niewykorzystujący losowości – który zlicza wszystkie spełniające przypisania dla tych zagadek w czasie subekspotencjalnym. Oznacza to, że ilość pracy rośnie wolniej niż jakakolwiek funkcja wykładnicza liczby zmiennych. Ponieważ zliczanie rozwiązań jest trudniejsze niż ustalenie, czy istnieje choć jedno rozwiązanie, wynik rozwiązuje również problem decyzyjny.

OpenAI poinformowało, że jego AI odkryło obalenie hipotezy 16 października, a 17 października wynik został sformalizowany w Lean – oprogramowaniu, które mechanicznie weryfikuje każdy krok logiczny. Artykuł i formalizacja są dostępne na GitHubie. OpenAI wskazało, że nastąpiło to po opublikowaniu wcześniej w tym miesiącu 722 rękopisów matematycznych, z których tylko 162 zawierało zweryfikowany komputerowo główny wynik. To właśnie ten format weryfikowalny maszynowo pozwala niezależnym badaczom samodzielnie sprawdzać każdy krok argumentacji.

Impagliazzo, Paturi oraz profesor MIT Ryan Williams kierują niezależnym badaniem twierdzenia. W otwartym liście zastrzegli, że ich udział nie powinien być interpretowany jako poparcie.

„Nasz udział nie powinien być traktowany jako certyfikacja tego twierdzenia” – napisali, dodając, że „wynik o takim znaczeniu wymaga starannej, niezależnej weryfikacji oraz zrozumienia, że inni mogą go odtwarzać, kwestionować i na nim budować.”

OpenAI poinformowało, że uczestnicy nie podpisali umów o zachowaniu poufności i pracują bez wynagrodzenia. Firma zobowiązała się również do opublikowania wszystkich surowych danych oraz sfinansowania konferencji poświęconej wynikowi.

Praktyczne konsekwencje pozostają niepewne. „Znalezienie takich algorytmów i przekucie postępów teoretycznych w praktyczne ulepszenia będzie wymagało dalszych znaczących badań” – napisało OpenAI. Artykuł wskazuje także, że wynik nie dowodzi, iż każdy problem w klasie złożoności NP może zostać rozwiązany w czasie subekspotencjalnym.

Oznacza to, że problem P versus NP pozostaje otwarty. P obejmuje problemy, które komputery mogą efektywnie rozwiązać, natomiast NP obejmuje problemy, dla których zaproponowane rozwiązania można efektywnie sprawdzić. Pytanie bez odpowiedzi brzmi: czy każdy problem, którego odpowiedź można efektywnie sprawdzić, można także efektywnie rozwiązać.

Anthropic wkroczył do dyskusji 26 października z artykułem przypisanym Claude'owi i zatytułowanym „A 2^o(n) Time Algorithm for 3-SAT”. Repozytorium, które również podejmuje problem ETH, wskazuje, że algorytm odkrył wewnętrzny badawczy model Claude. Dodaje, że „wynik ma czysto asymptotyczny charakter i nie mówi nic o rozwiązywaniu formuł w praktyce.”

Claude sformalizował Wielkie Twierdzenie Fermata w Lean we wrześniu. Matematyk Terence Tao ostrzegał wcześniej o możliwości nakładania się prac AI, pisząc we wrześniu: „Obserwowaliśmy już, że nawet plotka o tym, że ktoś pracuje nad problemem, może wywołać ogromny wysiłek napędzany AI, aby go 'spłaszczyć', zanim pierwotny projekt badawczy zdąży osiągnąć pełny potencjał.”

Niedawny wkład OpenAI w wysokości 5 milionów dolarów na rzecz Simons Foundation zasili warsztaty, konferencje i programy specjalne mające pomóc badaczom w analizie i rozwijaniu wyników wytworzonych przy udziale AI.

Źródło: Decrypt