AI udowodniło hipotezę z 2008 roku. Kto sprawdzi sprawdzającego?
Zacznijmy od liczby: osiemnaście lat. Tyle jedna z centralnych hipotez kwantowej teorii złożoności czekała na dowód. 6 listopada startup Physical Superintelligence ogłosił, że jego system badawczy, działający na niepublicznym modelu Anthropic, ten dowód znalazł. Hipoteza nazywa się Aaronsona-Ambainisa i krąży po tej dziedzinie od 2008 roku.
Ile to miało zająć maszynie? Według firmy kompletny dowód pojawił się w trzecim dniu pracy.
O co w ogóle chodzi?
Weź algorytm kwantowy, który zagląda do bitów wejścia tylko kilka razy. Prawdopodobieństwo, że odpowie „tak", okazuje się wielomianem o niskim stopniu względem tych bitów. Hipoteza mówi, że w takim grzecznym wielomianie zawsze znajdzie się choć jeden bit, który naprawdę coś znaczy: zmiana go zauważalnie przesuwa wynik.
A po co nam to? Bo jeśli to prawda, komputer kwantowy nie dostaje wykładniczej przewagi na losowych danych bez struktury. Wielkie kwantowe zwycięstwa muszą się brać z problemów, które jakąś strukturę mają. Już w sierpniu pojawiła się praca „Quantum Speedups Require Structure or Depth", która domknęła przypadek szczególny. Teraz ktoś mówi, że ma całość.
Skoro Lean to przyjął, to po sprawie?
I tu jest haczyk, o którym łatwo zapomnieć: skoro program do weryfikacji dowodów powiedział „OK", to co jeszcze można kwestionować?
Sporo. Lean sprawdza, czy każdy krok rozumowania jest poprawny, i robi to bezlitośnie. Nie sprawdza jednak, czy twierdzenie, które ktoś w nim zapisał, jest dokładnie tym samym, o co pytali matematycy. Jeśli formalna wersja jest odrobinę łatwiejsza od prawdziwej hipotezy, Lean z radością uzna dowód czegoś innego.
Dlatego ludzie muszą jeszcze przeczytać zapis formalny i potwierdzić, że się zgadza. Tekst artykułu też nie jest sprawdzony maszynowo. Firma podaje, że dowód przejrzał fizyk, a zespół, który w sierpniu domknął przypadek szczególny, też go obejrzał. Recenzji naukowej jeszcze nie było.
Czyli ile to jest warte?
Jeśli się utrzyma, bardzo dużo. System ponoć oparł się na znanych narzędziach, takich jak certyfikaty ułamkowe i zbiory poziomów, a potem został skierowany na pokrewne problemy, co dało jeszcze dwa ulepszenia, zanim Lean sprawdził wersję końcową. To nie wygląda na szczęśliwy strzał. To wygląda na pętlę badawczą.
Zwróć uwagę, jak zmienia się opowieść. Kiedyś trudno było znaleźć dowód. Teraz trudno uwierzyć temu, kto stoi obok niego z zielonym ptaszkiem. Najbliższe tygodnie czytania przez ekspertów rozstrzygną, czy 6 listopada będzie dniem, w którym hipoteza stała się twierdzeniem, czy dniem, w którym zobaczyliśmy, ile potrafi ukryć słowo „zweryfikowany".