Pierwszość liczby okazała się problemem wielomianowym
Przez lata istniały szybkie testy probabilistyczne pierwszości, lecz brakowało bezwarunkowego deterministycznego algorytmu wielomianowego znanego dla wszystkich wejść. Przełom przyniosła praca Manindry Agrawala, Neeraja Kayala i Nitina Saxeny: „PRIMES is in P”. Autorzy przedstawili deterministyczny algorytm działający w czasie wielomianowym względem długości binarnego zapisu liczby. To ważna lekcja o granicach wiedzy: fakt, że przez długi czas nie znamy szybkiego algorytmu, nie dowodzi, że problem jest fundamentalnie trudny. Trzeba też odróżniać testowanie pierwszości od faktoryzacji — to różne problemy o różnym znanym statusie złożoności.
Wejściem jest zapis liczby, nie sama jej wartość
Jeśli liczba N jest zapisana binarnie, długość wejścia wynosi około log2 N bitów. Naiwne dzielenie przez wszystkie liczby do √N jest więc wykładnicze względem liczby bitów, mimo że może brzmieć „tylko pierwiastek z N”. W teorii złożoności pytanie brzmi, czy czas można ograniczyć wielomianem długości zapisu, a nie wielomianem wartości N.
Przed AKS istniały świetne narzędzia
Testowanie pierwszości nie było przed 2002 rokiem praktyczną pustynią. Istniały efektywne testy probabilistyczne i metody deterministyczne działające pod dodatkowymi założeniami. Brakowało jednak ogólnego, bezwarunkowego dowodu istnienia deterministycznego algorytmu wielomianowego w standardowym modelu. To właśnie zmieniła praca Agrawala, Kayala i Saxeny.
„PRIMES is in P”
Artykuł opublikowany w Annals of Mathematics przedstawia bezwarunkowy deterministyczny algorytm wielomianowy rozstrzygający, czy liczba wejściowa jest pierwsza czy złożona. Wynik stał się klasycznym przykładem przesunięcia problemu do klasy P przez nową ideę, a nie przez szybszy hardware. To szczególnie istotne w podkategorii granic obliczeń, bo przypomina, że granicy nie wolno deklarować na podstawie braku pomysłu.
Pierwszość to nie faktoryzacja
Żeby stwierdzić, że N jest złożona, nie musimy w zadaniu PRIMES zwracać pełnego rozkładu na czynniki. Problem decyzyjny „prime czy composite?” i problem „podaj czynniki” nie są tym samym. Fakt, że pierwszy jest w P, nie daje automatycznie klasycznego wielomianowego algorytmu faktoryzacji. Mylenie tych zadań prowadzi do błędnych wniosków o kryptografii i złożoności.
Najważniejsza lekcja metodologiczna
W teorii złożoności „nie znaleźliśmy szybkiego algorytmu” jest stanem badań, a nie dowodem dolnej granicy. AKS pokazuje, jak problem może po latach otrzymać zupełnie nową klasyfikację dzięki matematycznej konstrukcji. Dlatego przy opisie otwartych problemów trzeba odróżniać twierdzenia udowodnione od przekonań i od aktualnie najlepszych znanych metod.
Dlaczego wersja deterministyczna była przełomem
Testy probabilistyczne potrafiły wcześniej bardzo szybko dawać niezwykle wiarygodną odpowiedź, ale ich analiza dopuszczała losowość i małe prawdopodobieństwo błędu albo wymagała dodatkowych założeń dla wariantów deterministycznych. Wynik AKS był innego rodzaju: pokazał bezwarunkowo, że problem PRIMES należy do P w deterministycznym modelu. Z punktu widzenia teorii złożoności chodziło więc nie o zastąpienie wszystkich praktycznych testów pierwszości, lecz o rozstrzygnięcie klasyfikacji problemu. To dobry przykład różnicy między algorytmem najwygodniejszym w praktyce a wynikiem, który ustala fundamentalną granicę teoretyczną.
AKS nie sprawił, że rozkład na czynniki stał się prosty
Łatwość testu pierwszości nie przenosi się automatycznie na znalezienie dzielników liczby złożonej. Możemy więc mieć efektywną odpowiedź na pytanie „czy N jest pierwsza?” bez znanego klasycznego algorytmu wielomianowego zwracającego rozkład dowolnej liczby na czynniki. To dobry przykład, jak subtelnie różnią się problemy decyzyjne i konstrukcyjne. Podobnie brzmiące zadania arytmetyczne mogą mieć inny status, dlatego klasyfikację trzeba przypisywać dokładnie sformułowanemu problemowi.