Konsekwencje quasi-wielomianowego algorytmu czasowego dla problemu izomorfizmu grafowego

40

Problemem wykres Izomorfizm (Gl) jest prawdopodobnie najbardziej znanym kandydatem na NP pośredniego problemu. Najbardziej znanym algorytmem jest algorytm subwykładniczy z czasem działania . Wiadomo, że GI nie jest -kompletny, chyba że hierarchia wielomianowa się załamie.2O(nlogn)NP

Jakie byłyby teoretyczne konsekwencje złożoności quasi-wielomianowego algorytmu czasowego dla problemu grafowego izomorfizmu?
Czy quasi-wielomianowy algorytm czasu dla GI obali jakiekolwiek znane przypuszczenia w teorii złożoności?


Inne podobne problemy, takie jak problem z minimalnym zestawem dominującym w turniejach, problem z izomorfizmem grupowym i problem z izomorfizmem turniejowym mają algorytmy quasi-wielomianowe ( QP ). Późniejsze dwa problemy można zredukować do GI w czasie wielomianowym.

Czy możemy skutecznie zmniejszyć problem minimalnego zestawu dominującego w turniejach do GI?
Czy istnieje przypuszczenie, że GI jest trudne dla QP?

Aktualizacja (14.12.2015) : Babai opublikował wstępny projekt dokumentu na arXiv dla swojego algorytmu quasipolynomial-time dla GI.

Aktualizacja (01.01.2017) : Babai wycofał twierdzenie, że algorytm działa w trybie quasipolynomialnym, zgodnie z nową analizą algorytm jest w czasie podwykładniczym który znajduje się w .expexp(O~(lgn))2no(1)

Aktualizacja (2017-01-09) : Babai przywrócił quasipolomomialną deklarację czasową, zastępując procedurę naruszania prawa bardziej wydajną.

Mohammad Al-Turkistany
źródło
6
Myślę, że wiele osób uważa, że ​​ma algorytm wielomianowy, a AFAIK taki algorytm nie miałby żadnych teoretycznych konsekwencji złożoności.
Huck Bennett,
7
Nie jest to dokładnie to, o co prosisz, ale jest to najlepsze, co wiem: grupowy izomorfizm ma naturalny i łatwy algorytm quasi-wielomianowy, ale prawdopodobnie nie ma redukcji z GI do GroupIso: eccc.hpi-web.de/report/2010/117 . Formalnie łatwiejsze pytanie niż to, o co pytasz, ale wciąż szeroko otwarte, to udowodnienie, że nie ma redukcji wielogodzinnej z GI na GroupIso. AC0
Joshua Grochow
14
Po dwóch latach uważam, że mamy odpowiedź. Laszlo Babai udowodnił, że GI ma quasi-wielomianowy algorytm czasowy. Źródło: lucatrevisan.wordpress.com/2015/11/03/…
user3415207
8
@ user3415207 Babai wycofał roszczenie dotyczące quasipolynomial runtime . Najwyraźniej wystąpił błąd w analizie.
Raphael
6
@ Rafael ... i Babai przywrócili swoje roszczenie (ten sam link, co twoje).
Danny

Odpowiedzi:

5

O ile mogę powiedzieć, jeśli zapytasz po prostu o konsekwencje samego faktu (jako czarnej skrzynki), że GI jest w QP, myślę, że odpowiedź jest bardzo niewielka. Jedyną rzeczą, o której mogę myśleć, która nie jest twierdzeniem, lecz konsekwencją kierunków badań, jest grupowy izomorfizm. Ponieważ GroupIso redukuje się do GI, a my nawet nie wiemy, czy GroupIso jest w P, umieszczenie GroupIso w P może być postrzegane jako ważna przeszkoda w umieszczeniu GI w P (jeśli sądzisz, że może tak być).

Ponieważ jednak trywialnym algorytmem dla GroupIso jest , w czasach, gdy złożoność GI wzrosła o , mieliśmy długi sposób na poprawę złożoności GI, zanim GroupIso stała się natychmiast istotną przeszkodą w umieszczeniu GI w P. Ale jeśli GI jest w QP, wówczas GroupIso staje się znacznie bardziej istotną przeszkodą dla dalszych ulepszeń GI. (Oczywiście wykładnik wykładnika w quasi-wielomianie jest nadal potencjalnie istotną luką, ale różnica staje się znacznie mniejsza, gdy GI jest w QP.)nlogn+O(1)2O~(n)

Joshua Grochow
źródło
Wydaje się, że nie jesteśmy w stanie poprawić znacznie słabszej górnej granicy testowania izomorfizmu płaszczyzn rzutowych ( ). Zobacz cstheory.stackexchange.com/questions/34773/…nO(loglogn)
Mohammad Al-Turkistany
@ MohammadAl-Turkistany: Tak, ale wtedy stosuje się ten sam argument: jeśli GI jest „droga” w quasipoli, to ProjPlaneIso jest bardzo daleka od przeszkody we wprowadzaniu GI do P. Gdy GI jest na czasie dla jakiegoś , wtedy ProjPlane również stałby się istotną przeszkodą. W tej chwili wydaje się, że GroupIso jest bardziej bezpośrednią przeszkodą - może kiedyś ProjPlane będzie również ...nO(loglogn)cc
Joshua
@JoshuaGrochow Czy zgodziłbyś się ze mną, że podejście przyjęte przez François Le Gall i Davida J. Rosenbauma w On the Group and Color Isomorphism Problems ma sens? A przynajmniej traktują niektóre pytania, które mogą pojawić się po podstawowym zrozumieniu wyniku László Babai?
Thomas Klimpel,
@ThomasKlimpel: Zgadzam się, że ich praca ma sens, chociaż nie widzę jeszcze, jak skorzystać z ich spostrzeżeń (pomimo zrozumienia większości dowodów Babai).
Joshua Grochow
Czy nie uważasz, że GI w QP ostatecznie doprowadziłoby do umieszczenia GI w ograniczonej klasie niedeterminizmu, takiej jak ? βkP
Mohammad Al-Turkistany
2

Odnośnie ostatniego pytania: twierdzenie o hierarchii czasu natychmiast implikuje, że QP nie ma pełnych problemów w przypadku wielomianowych redukcji wielomianowych lub Turinga. (Z drugiej strony, każdy problem oprócz i jest trudny do QP przy quasi-wielomianowych redukcjach.) Zatem, zakładając, że wynik Babai jest poprawny, GI nie jest twardy QP.Σ

Emil Jeřábek wspiera Monikę
źródło
0

Jakie byłyby teoretyczne konsekwencje złożoności quasi-wielomianowego algorytmu czasowego dla problemu grafowego izomorfizmu?

Mniej więcej podobne do konsekwencji deterministycznego wielomianowego algorytmu czasowego dla testowania pierwotności, deterministycznego wielomianowego algorytmu czasowego dla programowania liniowego oraz w innym przypadku, w którym znane były praktycznie wydajne (losowe) algorytmy (z rzadkimi przykładami patologicznymi, w których algorytm stał się nieefektywny) i używany przez długi czas. Potwierdza to przypuszczenie, że efektywność praktyczna jest dobrym wskaźnikiem na istnienie deterministycznych algorytmów teoretycznych przezwyciężających problemy rzadkich przykładów patologicznych.

Czy quasi-wielomianowy algorytm czasu dla GI obali jakiekolwiek znane przypuszczenia w teorii złożoności?

Nie, przypuszczenia raczej przechodzą na przeciwną stronę, mianowicie że GI jest w P. Ponieważ GI jest w NP, nie będzie możliwe obalenie tego typu przypuszczeń w najbliższym czasie.

Czy możemy skutecznie zmniejszyć problem minimalnego zestawu dominującego w turniejach do GI?

Minimalny zestaw dominujący nie jest problemem izomorficznym, dlatego nie ma powodu, dla którego należy oczekiwać, że będzie on redukowany do GI.

Czy istnieje przypuszczenie, że GI jest trudne dla QP?

Nie wiemy nawet, jak zredukować problem izomorfizmu strun do GI, a jest to przynajmniej problem z izomorfizmem. Dowód Babai wykazał, że izomorfizm strun dotyczy QP, więc ... A co jest trudne dla QP, co miałoby znaczyć? Ciężko w przypadku wielomianowego skrócenia czasu?


Od wprowadzenia „ O grupie i problemach z izomorfizmem kolorów” François Le Gall i Davida J. Rosenbauma

Złożoność problemów związanych z testowaniem izomorfizmu jest warta zbadania zarówno dlatego, że są to fundamentalne pytania obliczeniowe, jak i dlatego, że wiele z nich nie jest znanych z P, ale mimo to wydaje się łatwiejszych niż problemy z NP-zupełnością. Najbardziej szczegółowo zbadanym z nich jest problem izomorfizmu grafów.

Wierzyłem, że wiem, że wszystkie problemy z badaniem izomorfizmu struktur skończonych można sprowadzić do problemu izomorfizmu grafowego. Dlatego wierzyłem, że izomorfizm grafów jest „poprawnym ogólnym” problemem izomorfizmu, który rządzi nimi wszystkimi. Problem izomorfizmu strun zastosowany w pracy Babai'a ujawnił, że moje przekonanie nie było w pełni uzasadnione, ponieważ nadal nie wiadomo, czy problem izomorfizmu strun można sprowadzić do problemu izomorfizmu grafowego. Stąd uogólniony problem z izomorfizmem graficznym i uogólniony problem z izomorfizmem grupowymGIGrIsą zdefiniowane (w powyższym artykule, ale autorzy słusznie zastanawiają się, dlaczego nikt tego wcześniej nie zrobił), które dodają brakujące elementy z problemu izomorfizmu strun. (A problem z izomorfizmem kolorów to po prostu inna nazwa problemu z izomorfizmem strun. Problem z nazwami automorfizmu koloru wraca do początkowych prac Babai i Luksa, izomorfizm strun nazwanych występuje później w ich artykule na temat kanonicznego etykietowania.)

Ponieważ algorytm Babai'a był quasi-wielomianowym algorytmem czasowym dla problemu izomorfizmu łańcuchowego (tj. Dla ), konsekwencją było to, że testy izomorfizmu dla większości typów struktur skończonych powinny być całkiem wykonalne. Jednym z zastosowań takich badań izomorfizmu jest wykaz wszystkich różnych rodzajów struktur nieizomorficznych o określonych właściwościach w danym zakresie. Cóż, właściwie ta aplikacja działa znacznie lepiej z algorytmami kanonizacji (w przeciwieństwie do zwykłego testowania izomorfizmu dwóch danych struktur), ale dodatkowe spowolnienie nie zmieniłoby głównego wielomianu lub quasi-wielomianu związanego z tymi problemami.GI


Edycja: Ta odpowiedź została udzielona w kontekście wycofania wyniku Babai, zanim ogłosił poprawkę. Sugeruje to, że niewielkie uogólnienie problemu izomorfizmu graficznego sugerowane przez problem izomorfizmu strunowego jest naprawdę ważnym problemem. Oczekuje się tutaj domyślnie, że dowolny rozsądny algorytm dla problemu izomorfizmu grafu doprowadzi do podobnego algorytmu dla problemu uogólnionego grafu izomorficznego. Uogólniona problemem jest czas wielomian odpowiednikiem problemu set-stabilizator The Problem skrzyżowanie grupa , problem warstwa skrzyżowanie The Problem zestaw transportowy , ... Ideą jest oczekiwanie, że uogólniony problem będzie występować w rekurencyjnego częścikażdego rozsądnego algorytmu, więc i tak należy się nim zająć. (I jest całkiem możliwe, że uogólnionym problemem jest czas wielomianowy równoważny izomorfizmowi grafu).

Komentarze Joshua Grochowa wskazują, że nie udało mi się wyjaśnić pojęciowego znaczenia brakujących elementów problemu izomorfizmu strun. W przypadku struktur nieskończonych łatwiej zrozumieć, że prawidłowy izomorfizm powinien nie tylko zachować daną strukturę, ale także należeć do odpowiedniej kategorii funkcji (na przykład kategorii funkcji ciągłych). W przypadku struktur skończonych analogiczne zjawisko występuje najczęściej w przypadku struktur ilorazowych, w których odpowiednia kategoria funkcji powinna być zgodna z podanymi ilorazami. Materiał Johnsona jest typowym przykładem takich ilorazów, na przykład logika partycji działa na dwóch podzbiorach elementów niektórych zestawów podstawowych. Pamiętaj również, że ograniczenie dozwolonej kategorii izomorfizmów często ułatwia problem z testowaniem izomorfizmu,

Problem z uogólnieniami problemu izomorfizmu grafowego polega na tym, gdzie się zatrzymać. Dlaczego nie uogólnić do tego stopnia, że ​​obejmuje problem izomorfizmu grupy permutacji? To pytanie jest naprawdę trudne, ponieważ wiele nietrywialnych wyników dla izomorfizmu grafów prawdopodobnie przeniesie się również na izomorfizm grup permutacyjnych. Ale tutaj bardziej sensowne jest potraktowanie obliczeniowej teorii grup permutacyjnych jako odrębnego podmiotu, nawet jeśli ma ona rzeczywiście ścisły związek z problemem izomorfizmu grafu.

Thomas Klimpel
źródło
1
Po pierwsze, o ile rozumiem, łańcuch iso = kolor iso; jakie masz na myśli „sztuczne ograniczenia”? Po drugie, dobrze znanym wynikiem dotyczącym izomorfizmu wszystkich struktur skończonych redukujących się do GI jest stwierdzenie o strukturach skończonych możliwych do zdefiniowania w logice pierwszego rzędu. Izomorfizm łańcuchów / izomorfizm kolorów nie należy do tej klasy, ponieważ pyta nie tylko, czy dwa łańcuchy są izomorficzne jak struktury pierwszego rzędu, ale czy istnieje izomorfizm pierwszego rzędu między dwoma łańcuchami, w których izomorfizm leży w danej podgrupieSn .
Joshua Grochow
1
@JoshuaGrochow W przypadku koloru iso kolory to tylko dowolne liczby (wlog jest ograniczony do [n]). W przypadku iso ciągów, ciągi znaków są nad ustalonym skończonym alfabetem. Myślałem, że to binarny alfabet, ale źle to zapamiętałem. Właśnie przypomniałem sobie, że początkowo byłem zdezorientowany, czy kolor iso to po prostu inna nazwa dla string iso. Kiedy więc postanowiłem przeczytać ten artykuł po tym, jak Laszlo wycofał swoje roszczenie, wydawało mi się to różnicą. Może to naprawdę różnica, ponieważ „ponad skończonym alfabetem” komunikuje się „napraw swój ulubiony skończony alfabet, to nic nie zmieni”. Co jest prawdą.
Thomas Klimpel
1
Nawet jeśli wprowadzają to rozróżnienie, dwa problemy, które podajesz, są równoważne: na stałym skończonym alfabecie, po prostu użyj podciągów o długości aby zakodować kolory z , a następnie zmień grupę tak, aby zawsze przenosiła te podciągi jako całość. logn[n]
Joshua Grochow
1
@JoshuaGrochow To jest dokładnie to, co rozumiem przez to, że nie zrobi żadnej różnicy. ”To prawda. Próbowałem teraz odpowiedzieć na Twój komentarz„ Izomorfizm strun / izomorfizm kolorów nie mieści się w tej klasie ”. Z przyjemnością uczyłem się lekcji z Po drodze Andreas Blass i Yuri Gurevich, którzy również starają się skupić na punktach koncepcyjnych. Cieszę się, że Babai naprawił teraz swój algorytm, więc nie czuję obowiązku (ani presji), aby zbadać, czy izomorfizm wykresu i izomorfizm łańcucha są wielomianowymi równoważnikami czasu (W tym kontekście napisałem tę odpowiedź)
Thomas Klimpel,
Jestem zdezorientowany, dlaczego porównujesz postęp w zakresie GI z wynikami derandomizacji.
Sasho Nikolov