Konsekwencje quasi-wielomianowego algorytmu czasowego dla problemu izomorfizmu grafowego

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.$2^{O(\sqrt{n \log n})}$$\mathsf{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 .$\exp \exp(\tilde{O}(\sqrt{\lg n}))$$2^{n^{o(1)}}$

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

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.)$n^{\log n + O(1)}$$2^{\tilde O(\sqrt{n})}$

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.$\varnothing$$\Sigma^*$

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 grupowym$\mathsf{GI}^*$$\mathsf{GrI}^*$są 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.$\mathsf{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.