Informatycy o cal bliżej głównego celu algorytmicznego | Magazyn Quanta

Jeśli ktoś poprosi cię o ustalenie, czy dwa obiekty są takie same, może się to wydawać trywialną prośbą. W większości codziennych przypadków wystarczy szybki rzut oka, aby dokonać trafnej oceny.

Ale w informatyce jest to znacznie bardziej złożone pytanie. W rzeczywistości dotyczy to nierozwiązanego sedna tego, do czego zdolne są komputery. W zależności od tego, czym są obiekty i jak zdefiniujesz identyczność, nadal nie wiemy, czy komputery mogą szybko odpowiedzieć na pytanie, czy też powolne i pracochłonne podejście jest zasadniczo najlepszym, na co mogą sobie pozwolić.

W ciągu ostatniej dekady pojawiło się kilka ważnych wyników pokazujących, że komputery mogą działać przynajmniej trochę lepiej. Jeden z największe ostatnie wyniki w informatyce był szybszym algorytmem określania, kiedy dwa wykresy są takie same. Praca z 2015 r., reż Laszló Babai z University of Chicago przełamał jedną ważną barierę prędkości obliczeniowej, ale nie udało mu się pokonać innej.

A teraz artykuł pt Słońce Xiaorui z University of Illinois w Chicago przedstawił nowy, szybszy algorytm dla powiązanego problemu zwanego problemem izomorfizmu grupowego, który polega na określeniu, kiedy dwa obiekty matematyczne zwane grupami są takie same. Praca, opublikowana w Internecie w miniony marzec, robi mały krok w kierunku wyjaśnienia podstawowej złożoności obliczeniowej związanej z porównywaniem obiektów.

Praca Suna łamie obowiązujące od dawna ograniczenie prędkości dla określonej klasy grup — tę, która jest uważana za najtrudniejszy do rozwiązania problem izomorfizmu grupowego. Jeśli algorytm może szybko porównywać grupy tego rodzaju, można mieć nadzieję, że będzie w stanie szybko porównywać grupy dowolnego typu.

„Nie znamy takiego twierdzenia, ale mamy powody, by sądzić, że coś takiego powinno być prawdziwe” — powiedział Josha Grochowa z Uniwersytetu Kolorado w Boulder.

Porównanie porównań

Aby dokładnie określić, czy dwie rzeczy są takie same, musisz najpierw zdefiniować „to samo”. Dwa ciągi liczb można uznać za takie same, jeśli zawierają tylko te same cyfry lub mogą wymagać tych samych cyfr w tej samej kolejności.

Izomorfizm to szczególny rodzaj identyczności, który często pojawia się w matematyce. Kiedy dwa obiekty są względem siebie izomorficzne, oznacza to z grubsza, że ​​zawierają te same elementy i że elementy te są ze sobą w tej samej relacji.

Wykresy — zbiory wierzchołków (kropek) połączonych krawędziami (liniami) — zapewniają przystępny, wizualny sposób na zobaczenie, jak może wyglądać izomorfizm. Dwa grafy są izomorficzne, jeśli można dopasować wierzchołki jednego grafu do wierzchołków drugiego, tak że wierzchołki połączone krawędzią w pierwszym grafie są połączone krawędzią w drugim. Wykresy izomorficzne mogą wyglądać inaczej na powierzchni, ale mają wspólną podstawową strukturę.

Grupy są bardziej abstrakcyjne niż wykresy, ale nadal można je porównywać za pomocą izomorfizmu. Grupa to zbiór elementów — takich jak liczby — które można łączyć ze sobą zgodnie z pewną operacją, tak aby wynik również znalazł się w zbiorze. Na przykład możesz mieć grupę, której elementami są liczby całkowite — wszystkie dodatnie i ujemne liczby całkowite plus zero — i której działaniem jest dodawanie: dodaj dowolne dwie liczby całkowite, a wynikiem będzie zawsze inna liczba całkowita.

Dwie grupy są izomorficzne, jeśli można sparować każdy element z jednej grupy z elementem z drugiej, tak aby wynik działania na dwóch elementach z pierwszej grupy był zgodny z wynikiem działania na równoważnych wartościach tych elementów z drugiej Grupa.

Oto prosty przykład dwóch grup, z których każda zawiera dwa elementy, które są względem siebie izomorficzne. Pierwsza grupa składa się z cyfr 0 i 1, a druga grupa składa się z liter a i b. Obie grupy zawierają operację łączenia elementów grupy w określony sposób, której wyniki przedstawiono w poniższych tabelach.

Grupy są izomorficzne, ponieważ 0 tworzy pary z a, 1 para z b, a związek strukturalny utworzony przez połączenie elementów jest taki sam w obu grupach.

"Mówimy, że dwie grupy są izomorficzne, jeśli są zasadniczo równoważne" - powiedział Sun.

Niezrównoważony postęp

Izomorfizm jest ważną koncepcją w matematyce — gdzie grafy i grupy są szeroko rozpowszechnione — ponieważ pozwala matematykom spojrzeć poza powierzchowne różnice i skupić się na tym, w jaki sposób powiązane obiekty mogą być w rzeczywistości takie same. Ale ma to również fundamentalne znaczenie w informatyce; badacze nie tylko szukają algorytmów, które określają, czy dwa obiekty są izomorficzne, ale także mierzą, jak szybko te algorytmy mogą działać.

Ten pomiar może być trudny. Szybkość algorytmu zależy od tego, jak zmienia się jego czas działania wraz z rozmiarem obiektów, nad którymi pracuje. Wyobraź sobie na przykład, że masz dwie pary grup. W jednej parze każda grupa zawiera pięć elementów. W drugiej każda grupa zawiera 10 elementów.

Można by oczekiwać, że algorytm zajmie więcej czasu, aby określić, czy grupy z większą liczbą elementów są izomorficzne. Ale ile jeszcze czasu? Czy potrwa to dwa razy dłużej? 5² dłużej? 2⁵ dłużej? Pytania te odpowiadają ważnym szerokim klasyfikacjom prędkości algorytmicznej: mogą działać w czasie liniowym (co w tym przypadku oznacza, że ​​trwa dwa razy dłużej), w czasie wielomianowym (5² dłuższy) i wykładniczy (2⁵ dłużej).

Informatycy wiedzą, do której kategorii szybkości należy większość pytań dotyczących komputerów, ale nie wszystkie.

„Większość z nich jest najłatwiejsza lub najtrudniejsza [rodzaj pytań], ale nadal istnieje kilka wyjątków, które są nieznane” – powiedział Sun. Izomorfizm grafów i grup należą do tych wyjątków, co czyni je tak atrakcyjnymi do badania.

W 1970s, Roberta Tarjana z Uniwersytetu Princeton zdał sobie sprawę, że istnieje algorytm, który może określić, czy dowolne dwie grupy są izomorficzne z czasem działania $latex n^{{(log,n)}}$, gdzie n to liczba elementów w każdej grupie. Nazywa się to algorytmem czasu quasi-wielomianowego, aw hierarchii czasów wykonania jest lepszy niż czas wykładniczy (2ⁿ), ale gorszy niż czas wielomianowy (n²). Jest to w przybliżeniu taka sama prędkość jak algorytm izomorfizmu grafów Babai i nadal jest to najlepsze, co możemy zrobić dla grup prawie 50 lat później.

„Oznacza to z grubsza, że ​​przez pół wieku nie było postępu” — powiedział Sun.

W czasie, gdy Tarjan uzyskał wynik, problem izomorfizmu grupowego był szerzej badany niż wersja grafowa. Dzisiaj to się odwróciło, po części dlatego, że izomorfizm grafów pobudził ekscytujące innowacje, podczas gdy izomorfizm grupowy utknął w martwym punkcie.

„Wszystkie nasze narzędzia działały bardzo wolno przez lata i trudno było wykorzystać naszą wiedzę o algebrze [grup]”, powiedział James Wilson z Colorado State University.

Ale pomimo tej rozbieżności w postępie, te dwa problemy mają głębszy związek niż podobieństwo ich nazw: problem izomorfizmu grupowego (przynajmniej w tym sformułowaniu) sprowadza się do problemu izomorfizmu grafu. Oznacza to, że każdy algorytm, który może rozwiązać problem grafowy, może również rozwiązać problem grupowy w podobnym czasie. Odwrotna sytuacja nie jest prawdą — postęp w grupie nie oznacza postępu w wykresie. Ale brak postępów w problemie grupowym ciążył na matematykach poszukujących współmiernych korzyści w problemie grafów. Jak możesz osiągnąć coś trudniejszego, jeśli nie możesz najpierw osiągnąć czegoś, co jest blisko ze sobą powiązane i wydaje się jeszcze łatwiejsze?

„Innymi słowy”, powiedział Sun, „w celu dalszej poprawy izomorfizmu grafu, izomorfizm grupowy jest dużym wąskim gardłem”.

Przekształcenie problemu

Kiedy postępy w rozwiązywaniu problemu utknęły w martwym punkcie tak długo, jak w przypadku izomorfizmu grupowego, inwencja jest zwykle konieczna, aby się wydostać. „Kiedy masz duży postęp, powinno to być wskazówką, że pojawił się nowy pomysł” – powiedział Grochow.

Praca Suna zawiera kilka pomysłów, które obejmują skupienie się na ważnym typie grupy i znalezienie sprytnego sposobu na podzielenie tych grup na części w celu ich porównania.

Grupy, dla których pracuje algorytm Suna, to tzw p-grupy klasy 2 i wykładnik p. Są podobne do grup, w których iloczyn dwóch elementów jest innym elementem, a iloczyn pozostaje taki sam niezależnie od kolejności, w jakiej je mnożysz. Ale tak naprawdę liczy się to, co reprezentują dla ogólnego problemu izomorfizmu grupowego. Grupy te mają bardzo prostą strukturę, co oznacza, że ​​powinny być łatwe do porównania. Ale pomimo tej prostoty badacze nie wymyślili sposobu na przyspieszenie algorytmu. Dopóki nie mogli, wprowadzanie ulepszeń w ogólnej kwestii izomorfizmu grupowego wydawało się beznadziejne.

Sun zaczął od zmiany ustawienia z grup na macierze, tablice liczb, które służą jako podstawowe obiekty w algebrze liniowej. Było to możliwe dzięki twierdzeniu z lat trzydziestych XX wieku, zwanemu korespondencją Baera, które przekształca tę wersję pytania o izomorfizm grupowy w doskonale analogiczny problem dotyczący macierzy. W szczególności Sun pracował z przestrzeniami macierzowymi, które są zbiorami macierzy ze specjalną właściwością: (liniowa) kombinacja dowolnych dwóch macierzy w przestrzeni równa się innej macierzy w przestrzeni.

Innymi słowy, te przestrzenie mają strukturę bardzo podobną do grup. Więc zamiast próbować zrozumieć, kiedy dwie grupy są izomorficzne, Sun mógłby po prostu spróbować zrozumieć, kiedy dwie przestrzenie macierzowe są izometryczne — pojęcie izomorfizmu przestrzeni macierzowych, które odpowiada izomorfizmowi grup.

Sun nie był pierwszym badaczem, który zastosował to podejście, ale jako pierwszy wprowadził dodatkowy krok: podzielenie przestrzeni macierzowej na dwie części. Jeden kawałek jest rdzeniem przestrzeni, w której wszystkie matryce są proste. Drugi element to przestrzeń otaczająca ten rdzeń, w której wszystkie matryce są szczególnie złożone. Ten ruch odpowiada podziale grupy na podgrupy, które zawierają tylko niektóre z wszystkich elementów.

Następnie Sun zastosował różne metody algorytmiczne do każdego z tych elementów. Rdzeń ma prostą strukturę, więc użył charakterystyki struktury, aby przedstawić go w bardziej zorganizowany sposób. Zewnętrzna warstwa jest bardziej złożona, więc nie ma oczywistego szybkiego sposobu na porównanie jej z inną. Zamiast tego metoda Suna wykorzystuje podejście zwane indywidualizacją i udoskonalaniem, aby wykluczyć większość możliwych sposobów mapowania jednej zewnętrznej warstwy na drugą, a następnie wykorzystuje komputer do przepracowania wszystkich pozostałych możliwych sposobów określenia, czy istnieje dopasowanie izomorficzne.

Metoda jest podobna w duchu do rozwiązania łamigłówki sudoku. Istnieją kwadraty, których potencjalne wartości są ograniczone przez to, co już znasz (rdzeń przestrzeni macierzy), co pozwala szybko je wypełnić. Są też inne (warstwa zewnętrzna), które mają mniej ograniczeń, ale które można obliczyć, wypróbowując wszystkie możliwe wartości — i dopóki nie ma zbyt wielu tego rodzaju kwadratów, nadal można rozwiązać zagadkę w rozsądną ilość czasu.

„Wypełniam wszystkie rzeczy, o których mogę szybko powiedzieć, że są ograniczone, a teraz mogę wrócić i spróbować swoich sił w brakujących polach” – powiedział Wilson. „Jeśli zawęziłeś zakres, teraz jest dobry moment, aby zmienić bieg i użyć komputera do wyszukania właściwych wartości”.

Przełomem Suna było pokazanie, że zawsze można dokonać tego podziału dla odpowiednich przestrzeni macierzowych p-grupy klasy 2 i wykładnik p. Udowodnił następnie, że po takim podziale kombinacja technik algorytmicznych pozwala określić, czy dwie przestrzenie są izomorficzne w czasie $latex n^{{(log,n)}^{5/6}}$, czyli nieco niższy niż metoda $latex n^{{(log,n)}}$ Tarjana. (Oba algorytmy zawierają również stałe terminy, które nie mają dużego wpływu na czas wykonywania i które pominęliśmy dla przejrzystości).

Wynik nie określa, do której grupy kategorii prędkości należy izomorfizm; to wciąż gdzieś pomiędzy czasem wykładniczym a czasem wielomianowym. Ale Sun przesunął to nieco bliżej wielomianowej strony rzeczy i jest powód, by sądzić, że więcej niż to powinno być możliwe. W końcu jego praca dostarcza informatykom szybszego algorytmu izomorfizmu grupowego dla najtrudniejszych rodzajów grup, zwiększając prawdopodobieństwo, że podobne przyspieszenie może być w zasięgu grup wszelkiego rodzaju.

„Jeśli potrafisz to rozwiązać p-grupami, chyba da się to wszystko rozwiązać” – powiedział Grochow. "Może."