Model OpenAI obalił hipotezę czasu wykładniczego (ETH), odkrywając szybszą metodę rozwiązania klasycznej łamigłówki logicznej. Twierdzenie to potwierdza sprawdzony maszynowo dowód, podważający założenie, w które naukowcy wierzyli przez 27 lat.
Wynik ten nie dowodzi, że P równa się NP, co stanowi szersze zagadnienie leżące u podstaw współczesnego szyfrowania. W związku z tym algorytm nie stanowi bezpośredniego zagrożenia dla kryptografii zabezpieczającej Bitcoin (BTC) i Ethereum.
Dlaczego hipoteza czasu wykładniczego miała znaczenie?
Hipoteza dotyczy 3-SAT, zagadki złożonej z przełączników typu „prawda-fałsz” oraz reguł łączących je. Celem jest ustawienie przełączników, które jednocześnie spełnia wszystkie reguły.
Sprawdzenie proponowanej odpowiedzi jest łatwe. Znalezienie jej jest trudne, ponieważ każdy dodany przełącznik podwaja liczbę możliwych kombinacji.
Russell Impagliazzo i Ramamohan Paturi zaproponowali hipotezę ETH w 1999 roku. Pomimo wspólnego skrótu nie ma ona nic wspólnego z symbolem giełdowym Ethereum.
Hipoteza ta głosi, że w najgorszym przypadku żaden algorytm nie jest w stanie uniknąć tego wykładniczego wzrostu.
Badacze traktowali ją jako ścianę nośną. Według OpenAI setki artykułów z zakresu teorii grafów, biologii obliczeniowej i baz danych opierały swoje wyniki dotyczące trudności właśnie na tej hipotezie.
W jaki sposób sztuczna inteligencja znalazła skrót, którego nie dostrzegli eksperci?
16 października system OpenAI wygenerował dowód w języku naturalnym. Dzień później zespół sformalizował go w Lean, oprogramowaniu weryfikującym każdy krok logiczny.
Opublikowany algorytm przetwarza dane wejściowe zawierające n zmiennych w około 2^(n/√log n) krokach. Wynik ten przewyższa przewidywany przez ETH wykładniczy próg minimalny, jednak nadal jest zbyt powolny, by można go było wykorzystać w praktyce.
OpenAI ostrzega, że praktyczne przyspieszenie wymaga dalszych, szeroko zakrojonych badań.
Impagliazzo i Paturi, obaj z Uniwersytetu Kalifornijskiego w San Diego, będą teraz kierować przeglądem wraz z Ryanem Williamsem z MIT. Innymi słowy, autorzy hipotezy weryfikują jej obalenie.
Tymczasem OpenAI nie przypisuje sobie żadnych zasług naukowych za to odkrycie, co jest zgodne z podejściem przyjętym podczas wcześniejszej kontrowersji dotyczącej równań Naviera-Stokesa.
Scott Aaronson, profesor informatyki na Uniwersytecie Teksańskim w Austin, opowiedział o tym, jak dotarła do niego ta wiadomość.
„Moi studenci właśnie przyszli do mojego gabinetu, aby mi powiedzieć, że model OpenAI obalił hipotezę o czasie wykładniczym”
Scott Aaronson za pośrednictwem Shtetl-Optimized
Czy obalenie hipotezy czasu wykładniczego oznacza, że P równa się NP?
Nie. Problem P kontra NP dotyczy tego, czy każde zadanie, którego rozwiązanie można szybko sprawdzić, można również szybko rozwiązać.
Hipoteza czasu wykładniczego (ETH) była twierdzeniem bardziej rygorystycznym niż P ≠ NP. Dlatego jej obalenie pozostawia otwartą szerszą kwestię.
Wyobraź sobie górę między dwiema dolinami. Sztuczna inteligencja znalazła krótszą ścieżkę prowadzącą przez grzbiet, a nie tunel pod nim.
Greg Brockman, prezes i współzałożyciel OpenAI, zwrócił uwagę na tę samą kwestię kilka godzin po ogłoszeniu wyników.
To rozróżnienie ma znaczenie dla posiadaczy kryptowalut. Podpisy bitcoinowe opierają się na kryptografii krzywych eliptycznych, trudnym problemie matematycznym, którego ten algorytm nie rozwiązuje.
Benjamin Cowen, członek Rady Ekspertów ds. Analiz Rynkowych BeInCrypto, odniósł się do tej kwestii.
Aby jednak było jasne: obalenie hipotezy czasu wykładniczego nie dowiodłoby, że P = NP, ani nie oznaczałoby, że bezpieczeństwo Bitcoina lub Ethereum jest zagrożone.
Hipoteza czasu wykładniczego: co się stanie, gdy maszyny prześcigną swoich twórców?
Przekonania o niemożliwości już wcześniej ulegały załamaniu. W 1960 roku Anatolij Karatsuba obalił hipotezę Andrieja Kolmogorowa dotyczącą mnożenia w ciągu około tygodnia.
Podobnie Volker Strassen w 1969 roku postanowił udowodnić, że standardowe mnożenie macierzy jest optymalne, a zamiast tego odkrył szybszą metodę.
Różnica polega teraz na tym, kto znajduje skróty. Maszyny generują dowody, podczas gdy ludzie starają się je zrozumieć.
W tym samym komunikacie ogłoszono kolejne dowody z zakresu analizy harmonicznej i fizyki cząstek elementarnych.
To tempo ma duże znaczenie dla aktywów cyfrowych. Kryptograf Matthew Green ostrzegł już, że sztuczna inteligencja może osłabić matematyczne podstawy portfeli.
Cowen ujął tę szerszą lekcję w kategoriach rynkowych. Jego zdaniem dziedziny dalekie od finansów mogą ostatecznie zmienić oblicze rynków.
Dla branży opartej na założeniach dotyczących trudności każde przełomowe osiągnięcie w dziedzinie sztucznej inteligencji stanowi obecnie jednocześnie test warunków skrajnych.
