Czy można zdecydować o izomorfizmie grafowym za pomocą niedeterminizmu opartego na pierwiastku kwadratowym?

Ograniczonym nondeterminism łączy funkcję z klasy języków akceptowanych przez deterministycznych maszyny Turinga zasobach ograniczona, w celu utworzenia nowej klasy - . Ta klasa składa się z tych języków, które są akceptowane przez jakąś niedeterministyczną maszynę Turinga przestrzegającą tych samych granic zasobów, jakie są używane do zdefiniowania , ale gdzie może wykonywać co najwyżej niedeterministyczne ruchy. (Używam notacji Goldsmith, Levy i Mundhenk, zamiast oryginału Kintali i Fischera, a jest rozmiarem danych wejściowych.) $g(n)$ $C$ $g$ $C$ $M$ $C$ $M$ $g(n)$ $n$

Moje pytanie:

Czy istnieje stała taka, że GRAPH ISOMORPHISM znajduje się w - ? $c\ge0$ $c\sqrt{n}$ $\mathsf{PTIME}$

( Edycja: Joshua Grochow wskazał, że pozytywna odpowiedź na to pytanie oznaczałaby algorytm dla GI, który ma lepsze asymptotyczne granice środowiska wykonawczego niż są obecnie znane. Dlatego chętnie rozluźniłbym granicę, umożliwiając niedeterministyczne ruchy). $o(\sqrt{n}\log n)$

tło

Dla każdej stałej stałej , - , ponieważ niedeterministyczne ruchy tworzą co najwyżej wielomianową liczbę konfiguracji do eksploracji deterministycznej. Ponadto , a za pomocą wypełnienia można wyświetlić języki NP-complete w - dla każdego . $c \ge 0$ $\mathsf{PTIME} = {c\log n}$ $\mathsf{PTIME}$ $c\log n$ $\mathsf{NP} = \cup_c n^c\text{-}\mathsf{PTIME}$ $n^\varepsilon$ $\mathsf{P}$ $\varepsilon > 0$

Kintala i Fischer zauważyli, że decydowanie, czy wykres wejściowy z wierzchołkami ma kliknięcie jest -kompletny, ale jest w - . Aby to zobaczyć, odrzuć wierzchołki, które mają najwyżej sąsiadów. Jeśli pozostało zbyt mało wierzchołków, odrzuć. W przeciwnym razie pozostałe wierzchołki tworzą wykres wielkości . Następnie zgadnij podzbiór wierzchołków za pomocą niedeterministyczne kroki i sprawdź, czy tworzą one klikę w czasie wielomianowym. $V$ $(|V|/3)$ $\mathsf{NP}$ $O(\sqrt{n})$ $\mathsf{PTIME}$ $|V|/3 - 2$ $\Omega(|V|^2)$ $|V|/3$ $|V| = O(\sqrt{n})$

Niektóre inne języki gęstych wykresów w są również w - . Dzieje się tak w przypadku każdego problemu, w którym podzbiór wierzchołków służy jako certyfikat, a rozmiar wykresu wejściowego to . Przykładami są obiecujące wersje Induced Path lub 3-Coloring w przypadku gęstych wykresów. Wydaje się, że inne problemy wymagają większych certyfikatów, na przykład lista wierzchołków definiujących obwód hamiltonowski wydaje się wymagać bitów . Nie jest dla mnie jasne, czy można użyć niedeterminizmu, który jest zbyt mały, aby odgadnąć certyfikat, aby rozstrzygnąć takie problemy. $L$ $\mathsf{NP}$ $O(\sqrt{n})$ $\mathsf{PTIME}$ $\Omega(|V|^2)$ $\Omega(|V| \log |V|)$

Biorąc pod uwagę, że - może zawierać języki NP-zupełne, wydaje się interesujące zapytać, gdzie w ograniczonej hierarchii niedeterminizmu spadają potencjalnie łatwiejsze języki. Można się spodziewać, że GI, jako język, który nie wydaje się być NP-zupełny, będzie w hierarchii bliżej - niż - . Jednak oczywisty certyfikat dla GI określa mapę za pomocąbitów, czyli . $n^\varepsilon$ $\mathsf{P}$ $\log n$ $\mathsf{P}$ $n$ $\mathsf{P}$ $|V|\log |V|$ $\omega(\sqrt{n})$

Inny sposób myślenia o tym pytaniu: czy określenie mapy między zestawami wierzchołków jest najkrótszym możliwym certyfikatem dla GI?

Edycja: Poniżej podano kilka (poprawionych) uwag, które odnoszą się do komentarzy Jozuego Grochowa.

Jeśli certyfikat używa bitów i może być sprawdzany w czasie wielomianowym, wówczas brutalna siła daje algorytm dla GI przyjmującego czas. W przypadku certyfikatu o rozmiarze brute force daje algorytmowi zajmowanie czasu, zaś certyfikat o rozmiarze daje podejście z użyciem siły brutalnej, zajmując czasu. Długotrwała górna granica Luksa to czas, który jest między tymi dwiema granicami aż do stałych wykładników. $f(n) = \Omega(\log n)$ $poly(n)2^{O(f(n))} = 2^{O(f(n))}$ $O(\sqrt{n})$ $2^{O(\sqrt{n})}$ $O(\sqrt{n}\log n)$ $2^{O(\sqrt{n}\log n)}$ $2^{O(\sqrt{n\log n})}$

Te rozważania sugerują, że może istnieć alternatywne podejście do OG. Podejście Luksa wydaje się opierać na identyfikacji podzbioru generatorów powiązanej grupy. Maszyna niedeterministyczna może zatem odgadnąć podzbiór grupy. Te podzestawy można następnie dokładnie sprawdzić, aby uzyskać algorytm deterministyczny. Jeśli listę elementów można określić zwięźle, albo dlatego, że powiązana grupa nigdy nie jest dużo większa niż rozmiar wykresu, lub ponieważ liczba wymaganych generatorów jest zawsze niewielka, a sprawdzenie każdego podzbioru kandydata nie trwa zbyt długo, wówczas może dać alternatywne podejście do OG.

Chandra MR Kintala i Patrick C. Fischer, Refining Nondeterminism in Relativized Polynomial-Time Bounded Computation , SIAM Journal on Computing 9 (1), 46–53, 1980. doi: 10.1137 / 0209003
Judy Goldsmith, Matthew A. Levy, Martin Mundhenk, Ograniczony niedeterminizm , SIGACT News 27 (2), 20–29, 1996. doi: 10.1145 / 235767.235769
László Babai i Eugene M. Luks, Canonical Labeling of Graphs , STOC 1983, 171–183. doi: 10.1145 / 800061.808746

cc.complexity-theory graph-theory graph-isomorphism nondeterminism András Salamon
źródło

Zatem jeśli wykres jest podany jako macierz przylegania o rozmiarze czy to oznacza, że mogę wykonać liniową liczbę niedeterministycznych ruchów wrt do rozmiaru zestawu wierzchołków ?

n^{2}

$n^2$

n

$n$

John D.

@ user17410: Tak, reprezentacja nie powinna mieć większego znaczenia, o ile rozmiar dowolnej instancji wynosi . (Jeśli są nieracjonalnie wyściełane mieć rozmiar . Następnie oczywiście pierwiastek związany jest dostatecznie)

O (| V |^{2})

$O(|V|^2)$

Ω ((| V | \log | V |)^{2})

$\Omega((|V|\log|V|)^2)$

András Salamon

Myślę, że możesz poprosić o algorytm lepiej niż najbardziej znany ... Jeśli rozumiem, algorytm dałby algorytm deterministyczny. Obecny najbardziej znany algorytm deterministyczny wymaga czasu .

O (\sqrt{n}) - P T I M E

$O(\sqrt{n})-\mathsf{PTIME}$

2^{O (\sqrt{n})}

$2^{O(\sqrt{n})}$

2^{O (\sqrt{n} \log^{2} n)}

$2^{O(\sqrt{n} \log^2 n)}$

Joshua Grochow

@ AndrásSalamon: Brute force = NOT ... Poza tym nie widzę, dlaczego certyfikat wielkości prowadzi do algorytmu brutalnej siły czasu zamiast - czy możesz opracować? Może brakuje mi czegoś w definicji zapisu „PTIME”?

n! p o l y (n) \approx 2^{O (n \log n)}

$n!poly(n) \approx 2^{O(n \log n)}$

2^{O (\sqrt{n} \log^{2} n)}

$2^{O(\sqrt{n} \log^2 n)}$

\sqrt{n}

$\sqrt{n}$

2^{\sqrt{n} \log n}

$2^{\sqrt{n} \log n}$

2^{O (\sqrt{n})}

$2^{O(\sqrt{n})}$

Joshua Grochow

@ MohammadAl-Turkistany: Może, ale muszę się nad tym zastanowić. W algorytmie Babai są punkty, w których, gdy stopień koloru jest poniżej polilogu, stosuje test GI z ograniczeniem-deg, podobnie jak w poprzednim najlepszym algorytmie, i nie jest jasne, czy można przekształcić test z polilog-deg w ograniczenie do polilogu niedeterminizm, czyli czy można kontynuować rekurencję Babai dalej, aby sprowadzić stopień do, powiedzmy, stałego stopnia koloru. Jeśli i kiedy to wymyślę, zaktualizuję moją odpowiedź - jeśli masz przemyślenia na ten temat, chętnie porozmawiam, ale prawdopodobnie nie jest to odpowiednie miejsce do pracy.

Joshua Grochow

Po pierwsze, (jak już edytowano w pytaniu) pozytywna odpowiedź na twoje pytanie natychmiast poprawiłaby stan techniki w najgorszych przypadkach dla izomorfizmu grafowego. Dla algorytmu daje algorytm czasie , ale obecnie najbardziej znany z GI to tylko $O(\sqrt{n})-\mathsf{PTIME}$ $2^{O(\sqrt{n})}$ $2^{O(\sqrt{n \log n})}$

Po drugie, nie jest nawet od razu jasne, czy obecnie najlepszym algorytmem jest w rzeczywistości algorytm , chociaż jego pierwsza część jest wyraźnie jakiś sens. Algorytm najpierw zgaduje zestaw wierzchołków o rozmiarze celu zindywidualizowania (sztuczka Zemlyachenko - zobacz tutaj ekspozycję w języku angielskim), co można zrobić zgadując bitów niedeterministycznie . Jednak po ich odgadnięciu i zindywidualizowaniu (w deterministycznym czasie wielorakim) stosuje najbardziej znany test izomorfizmu stopnia ograniczonego, który zajmuje czas (Twierdzenie 9.1 tego artykułu ), i stosuje to w przypadku $O(\sqrt{n \log n})-\mathsf{PTIME}$ $\sqrt{n/\log n}$ $\sqrt{n \log n}$ $n^{O(d /\log d)}$ $d=O(\sqrt{n \log n})$ . Musiałbym dokładnie przemyśleć, czy ten ostatni algorytm można przekształcić w algorytm (wydaje się interesujące pytanie ...) $O(\sqrt{n \log n})-\mathsf{PTIME}$

Joshua Grochow
źródło

Czy masz linki do wersji nie za zaporą? Nigdy nie widziałem rzeczywistej realizacji sztuczki Zemlyachenko ani testu izomorfizmu z ograniczonym stopniem. Partycjonowanie wierzchołków według stopnia jak NAUTY przyspiesza rzeczy, ale ci z tym samym stopniem nadal muszą sprawdzić wszystkie permutacje cyklu głównego na nich AFIK.

Chad Brewbaker

@Chad: Niestety nie znam wersji tych artykułów nieobsługiwanych przez system płatniczy. Jednak sztuczka Zemlyachenko jest dość prosta do wdrożenia w praktyce i zasadniczo zmniejsza stopień. Myślę, że jedynym praktycznym zastosowaniem sztuczki Zemlyachenko jest kompromis między wyliczaniem zbiorów wierzchołków w celu zindywidualizowania (wykładniczy w rozmiarze zbioru) a wszelkimi potencjalnymi korzyściami uzyskanymi poprzez skuteczne zmniejszenie stopnia. Nie wiem, czy jest on faktycznie zaimplementowany w NAUTY, czy w innych praktycznych algorytmach izomorfizmu.

Joshua Grochow

@Chad: Nawiasem mówiąc, testowanie permutacji cyklu podstawowego wystarcza tylko do wykrycia nietrywialnego automorfizmu; nie wystarczy do badania izomorfizmu. Na przykład, jeśli jest wykresem bez nietrywialnych automorfizmów, niech będzie dowolną permutacją - niekoniecznie pierwotnym cyklem. Zatem jest izomorficzny do , a jest jedynym izomorfizmem między i . Ale ten izomorfizm nie zostałby wykryty, biorąc pod uwagę tylko cykle pierwsze.

G

$G$

π

$\pi$

π (G)

$\pi(G)$

G

$G$

π

$\pi$

G

$G$

π (G)

$\pi(G)$

Joshua Grochow

Kosztem podwojenia , ISO można obliczyć za pomocą AUT, umieszczając oba wykresy w macierzy sąsiedniej.

n

$n$

Chad Brewbaker

@Chad: Jeśli to zrobisz, to jest jużpermutacje cyklu pierwszego rzędu 2, więc straciłeś wszelkie potencjalne oszczędności. Jest to związane z faktem, że opisywana redukcja dotyczy ISO do obliczenia zespołu generującego grupę automorfizmów. Nie jest znane ograniczenie wieloczasowe od ISO do problemu polegającego jedynie na decydowaniu, czy wykres ma nietrywialny automorfizm.

n!

$n!$

Joshua Grochow

Czy można zdecydować o izomorfizmie grafowym za pomocą niedeterminizmu opartego na pierwiastku kwadratowym?

tło

Odpowiedzi: