Zagadka teorii liczb, nad którą ludzkość utknęła na dziesięciolecia — czy AI rozwiązała ją w zaledwie 8 stronach?
Przez ostatnie dwa dni całe środowisko matematyczne i kręgi informatyki były w ogromnym szoku.
18 października słowa teoretyka liczb ze Stanford University, Jareda Dukera Lichtmana, na X natychmiast wznieciły pożar w całym internecie —
„Istnienie takiego dowodu silnie sugeruje P≠NP”.
Bezpośrednim powodem tego stwierdzenia był zdumiewający arkusz odpowiedzi dostarczony właśnie przez wewnętrzny model OpenAI — dowód, że „nie istnieje zero Landaua-Siegela”.
Ten kluczowy problem analitycznej teorii liczb, nad którym utknięto na dziesięciolecia, jest powszechnie uznawany przez środowisko akademickie za niezwykle trudny.
W rezultacie nie tylko OpenAI go rozwiązało, ale oryginalny dowód liczył właściwie zaledwie 8 stron!
Potem nastąpiły jeszcze bardziej ekscytujące wydarzenia. Czołowi matematycy szybko podjęli temat:
Bill Banks z University of Missouri najpierw napisał szczegółowe, 19-stronicowe omówienie;
Zaraz potem Bryce Kerr użył rozszerzeń dwukwadratowych
i klasycznych wyników Massera, aby skompresować dowód do 6 stron;
Następnie profesor University of Oxford Ben Green skrócił go ponownie, dając bezpośrednio ostateczną 5-stronicową wersję!
Od dziesięcioleci beznadziejnej nierozwiązywalności do zaledwie 5 stron. Profesor Abhishek Saha z Queen Mary University of London postawił pytanie poruszające sumienie:
Jeśli ten problem można udowodnić w zaledwie 5 stronach, dlaczego matematycy przeoczyli go przez dziesięciolecia?
Znaleźć go to jak wspiąć się do nieba, zweryfikować go to jak wypić wodę
Dlaczego 5-stronicowy dowód z teorii liczb miałby sprawić, że profesor ze Stanford od razu pomyśli o świętym Graalu informatyki — P vs NP?
Powód jest prosty.
5-stronicowy dowód może przeczytać i zweryfikować każdy ekspert w kilka godzin; ale nad tymi 5 stronami najjaśniejsze umysły ludzkości zmagały się przez dziesięciolecia.
„Znalezienie jest niezwykle trudne, weryfikacja jest niezwykle łatwa”. Te osiem słów to dokładnie podstawowa intuicja P≠NP!
W sekcji komentarzy badacz Anthropic Joshua Batson wskazał przenikliwie —
Matematyczne „oczywiste” jest zawsze względne. Fakty dowiodły, że wiele nierozwiązanych problemów (względem AI) jest całkowicie oczywistych!
Za żartem kryje się niezwykle poważne pytanie: kiedy AI dostarcza ponad 700 rękopisów matematycznych w ciągu kilku tygodni, czy problem milenijny P vs NP również nadchodzi?
Trzy wysokie mury, które zamykały ludzkość na pięćdziesiąt lat
Wyjaśnić P vs NP w jednym zdaniu: Czy wszystkie problemy, których odpowiedzi można szybko zweryfikować, są także problemami, których odpowiedzi można szybko obliczyć?
P to zbiór problemów, które „można szybko rozwiązać”, a NP to zbiór problemów, które „można szybko zweryfikować”.
Sudoku, układanie planu zajęć i łamanie haseł – wszystko to należy do NP: dajesz odpowiedź, a w ciągu sekundy możesz sprawdzić, czy jest poprawna czy błędna; ale żeby znaleźć ją od zera, możesz zrobić tylko coś bliskiego wyczerpującemu przeszukiwaniu.
Gdyby P=NP, współczesna kryptografia natychmiast by się zawaliła, globalne finanse zostałyby całkowicie odsłonięte, ale wszystkie złożone problemy zyskałyby ostateczny skrót;
Gdyby P≠NP, oznaczałoby to, że wszechświat zawiera problemy, których zasadniczo nie da się skrócić.
Problem ten został postawiony w 1971 roku, z nagrodą 1 miliona dolarów. Zdecydowana większość naukowców wierzy, że P≠NP, ale od ponad pięćdziesięciu lat nikomu nie udało się tego udowodnić.
Gdzie tkwi trudność? Ponieważ ludzkość nie tylko nie zdołała znaleźć klucza, ale wręcz udowodniła, że istniejące narzędzia do otwierania zamków są skazane na nieskuteczność.
To są słynne trzy „bariery”:
1. Bariera relatywizacji (1975): klasyczne metody opierające się na symulacji i diagonalizacji po prostu nie mogą tego rozwiązać;
2. Bariera naturalnych dowodów (1994): większość podejść dowodowych dla dolnych ograniczeń obwodów, gdyby mogły udowodnić P≠NP, przypadkowo złamałyby generatory liczb pseudolosowych, prowadząc do sprzeczności;
3. Bariera algebraizacji (2008): ulepszone metody połączone z technikami algebraicznymi również zostały udowodnione jako mające niewystarczającą siłę rażenia.
W czerwcu tego roku teoretyk złożoności Lance Fortnow stwierdził pesymistycznie: obecnie ludzkość nie ma nawet wykonalnej drogi ataku.
Zasugerował, aby challengerzy najpierw udowodnili znacznie prostszy problem, taki jak „SAT nie ma algorytmu kwadratowego”, a następnie dodał cios kończący: „Tam też wam się nie uda”.
To jest przeciwnik, z którym musi się zmierzyć AI.
719 manuskryptów bombarduje mury, 9-letni prodigy podchodzi tuż blisko
W obliczu murów z brązu i żelaza AI natychmiast rozpoczęła atak nasyceniowy.
6 października OpenAI opublikowało jednocześnie 722 manuskrypty na GitHubie (3 zostały wycofane następnego dnia), sklasyfikowane w 372 rodzinach wyników.
Wewnętrzny model wypróbował około 4000 otwartych problemów, średnio tylko około 3 godzin mocy obliczeniowej ChatGPT Pro na problem.
Wśród nich teoretyczna informatyka stanowiła 40 rodzin. Chociaż nie rozwiązała bezpośrednio P vs NP, kilka prac trafiło precyzyjnie na główne drogi do niego prowadzące.
W czerwcu tego roku teoretyk złożoności Lance Fortnow napisał: poza symulacją nie mamy sposobu na radzenie sobie z ogólnymi algorytmami wielomianowymi; złożoność obwodów, złożoność dowodów, geometria algebraiczna i inne ścieżki są wszystkie zablokowane znacznie poniżej pełnej mocy czasu wielomianowego. Jego wniosek był taki, że obecnie nie ma nawet jednej wykonalnej drogi ataku. Coincidence, sześć wyników OpenAI tym razem zasadziło flagę na każdej z nich.
Rodzina nr 112 (dolne ograniczenia obwodów głębokości 3): Najbardziej obiecującą drogą do udowodnienia P vs NP jest udowodnienie, że pewien problem NP wymaga „obwodów o superwielomianowym rozmiarze”. Ludzkość od dawna utknęła na
dotyczących jawnych dolnych ograniczeń dla obwodów głębokości 3; tym razem AI bezpośrednio przekroczyła ten próg.
Rodzina nr 102 (Hipoteza unikalnych gier, UGC): Udowodniono tę kluczową hipotezę zaproponowaną przez Subhasha Khota w 2002 roku (w tym częściową weryfikację w Lean). Jest ona blisko powiązana z P vs NP i znacznie wzmacnia granice nieaproksymowalności wielu trudnych optymalizacyjnych problemów NP.
Algorytmy fundamentalne i derandomizacja: Osiągnięto pełną derandomizację randomizowanej przestrzeni logarytmicznej (L=RL=BPL); skompresowano wykładnik mnożenia macierzy do
; mnożenie liczb całkowitych i DFT spadły poniżej
czasu.
Wokół Rodziny nr 102, „Hipotezy unikalnych gier”, miała miejsce również przeszywająca serce scena.
Dana Moshkovitz, żona słynnego uczonego Scotta Aaronsona, poświęciła całą swoją karierę tej hipotezie. W noc publikacji ich 9-letni syn podbiegł, aby zadrwić z matki:
„Słyszałem, że robot rozwiązał problem, nad którym pracowałaś całe życie!”
Quanta Magazine ujawniło również, że zespół Dor Minzera z MIT, po usłyszeniu plotek o OpenAI 11 września, pospieszył się z opublikowaniem własnego dowodu powiązanego wariantu przed publikacją OpenAI, aby nie zostać wyprzedzonym przez maszynę.
Ludzcy matematycy już zaczęli ścigać się z AI.
Wielkie sławy leją zimną wodę: Zewnętrzne miasto zdobyte, brama miejska nieprzełamana
Jednak eksperci, którzy najlepiej znają tę dziedzinę, są najspokojniejsi.
Lance Fortnow opublikował następnego dnia artykuł, wskazując: współczynnik rozwiązywania danych problemów przez AI wynosi mniej niż 10%, a żaden z tych wyników nie przybliża nas do rozwiązania P vs NP.
Chociaż Scott Aaronson nazwał 6 października „jednym z najważniejszych dni w historii matematyki”, wskazał również: na liście brakuje nie tylko P≠NP, ale także „mniejszych” trudnych problemów, takich jak P=BPP—oczywiście nie dlatego, że nikt nie próbował.
Ujawnił w podcaście: OpenAI i Anthropic używają swoich najpotężniejszych wewnętrznych modeli, aby ścigać się w kierunku złamania P vs NP, ale żadnemu z nich jeszcze się to nie udało.
Patrząc na to spokojnie, przed przełomem wciąż stoi cztery główne trudne przeszkody:
1. Weryfikacja jest daleka od ukończenia: tylko około 42% ma sformalizowane dowody w Lean, a reszta opiera się całkowicie na pracy ręcznej. Aaronson przyznaje, że prawie żaden człowiek tak naprawdę nie zrozumiał żadnego z tych długich dowodów.
2. Czytelność jest niezwykle słaba: Moshkovitz skomentowała, że jedyny dowód gry napisany przez AI został napisany „tak źle, że nie da się go zrozumieć bez pomocy AI”.
3. Lean nie jest wszechmocny: maszyny mogą jedynie zagwarantować, że rozumowanie jest poprawne, ale nie mogą zagwarantować, że sformalizowane definicje są całkowicie zgodne z pierwotnym problemem, ani nie mogą ocenić, czy wynik jest ważny.
4. Główna ścieżka pozostaje pusta: to, co AI przełamało, to obwody o głębokości 3 i obwody algebraiczne, podczas gdy „ogólne dolne granice dla obwodów boolowskich”, które mogłyby implikować P≠NP, pozostają niezapisane.
Ostateczny paradoks: czy AI jest żywym dowodem na P≠NP?
Skoro brama miasta nie została wyłamana, dlaczego wciąż mówi się, że „AI się zbliża”?
Ponieważ trzy sygnały są już nieporównywalnie jasne.
Po pierwsze, „trudność” trudnych problemów została na nowo wyceniona. Pięciostronicowy dowód zera Siegela pokazuje, że w niektórych ślepych zaułkach brakuje tylko tego jednego kroku, na który nikt nie wpadł. Ile przypuszczeń dzieli tylko jedna warstwa papieru? Nikt nie jest pewien.
Po drugie, pozycje peryferyjne rozkwitają wszędzie. Unikalne gry, dolne granice obwodów, derandomizacja, mnożenie macierzy... te kamienie milowe na pozycjach otaczających zostały intensywnie zdobyte przez AI, a główny kierunek prędzej czy później zostanie przełamany.
Po trzecie, skala i szybkość nie są rzędu wielkości człowieka. 4000 problemów, średnio 3 godziny każdy. Kiedy główne laboratoria skierują następną generację swojej najpotężniejszej mocy obliczeniowej prosto na P vs NP, akumulacja ilościowa z dużym prawdopodobieństwem wywoła zmianę jakościową.
Co do ostatecznego wyniku, w środowisku akademickim pojawiły się nawet ciekawe różnice zdań w zakładach.
Aaronson wciąż mocno obstawia P≠NP; ale niektórzy uczeni uważają, że jeśli AI naprawdę może dokonać przełomu, odpowiedź częściej będzie P=NP — ponieważ skłonienie AI do wyszukania sprytnego algorytmu jest znacznie łatwiejsze do wyobrażenia niż użycie istniejącej matematyki do udowodnienia „niemożliwości”.
Jednak najbardziej intrygującą i humorystyczną częścią całej sprawy jest —
Im potężniejsze staje się AI, tym bardziej ono samo wygląda jak żywy dowód na P≠NP.
Zużywa ogromną moc obliczeniową, aby „wyszukiwać” dowody, podczas gdy ludzie spędzają kilka godzin, aby „zweryfikować” wyniki.
Jeśli pewnego dnia AI naprawdę wypali swoją moc obliczeniową i udowodni P≠NP, będzie to najdoskonalszy dowód samego siebie tego milenijnego problemu.
Ten artykuł pochodzi z publicznego konta WeChat „Xinzhiyuan”, autor: ASI Revelation
