„Mały” wykres izomorfizmu

19

Myśląc o złożoności testowania izomorfizmu wykresów asymetrycznych (patrz moje powiązane pytanie dotyczące cstheory), przyszło mi do głowy pytanie uzupełniające.

Załóżmy, że mamy do wielomianu czasu maszynowego Turinga , który na wejściu generuje wykres G M , n z n węzłów.M1nGM,nn

Możemy zdefiniować problem ΠM :

(„Małe” GI): Biorąc pod uwagę wykres G=(V,E) , oznacza G izomorficzny na GM,|V|?

Innymi słowy musimy porównać dany wykres z „odniesienia” wykresie tej samej wielkości generowanej przez stałej wielomian czasu maszyna Turinga M .

Dla wszystkich czasie wielomianowym maszyny Turinga M , mamy ΠMNP , a dla wielu z nich mamy ΠMP .
Ale czy to prawda dla wszystkich M ? Czy problem jest znany?

Na pierwszy rzut oka myślałem, że każdy ΠM powinien być znacznie łatwiejszy niż GI , ponieważ dla każdego n istnieje tylko jeden wykres „odniesienia” o tej wielkości i być może symetrie / asymetrie wykresów generowanych przez M mogą być wykorzystane i można zbudować wydajny tester izomorfizmów ad-hoc ... ale to nieprawda: M może zawierać pewnego rodzaju uniwersalną maszynę Turinga o wielomianach czasowych, która wykorzystuje (jednoargumentowy) sygnał wejściowy 1n do generowania zupełnie innych (w strukturze) wykresów referencyjnych jako n wzrasta.

Marzio De Biasi
źródło
Ciekawe Znasz przykładowy P czasie maszyna Turinga , który generuje wykres G M , N ? MGM,N
Mohammad Al-Turkistany
@ MohammadAl-Turkistany: Trywialny przykład, dla którego , to TM M, które po prostu wyprowadza n izolowanych wierzchołków (lub inny to TM, który wyprowadza K n ). Bez utraty ogólności możemy również pomyśleć o modelu, w którym każdy czas wielomianowy TM nad binarnym alfabetem generuje wykres referencyjny: wystarczy wybrać pierwsze n 2 bity taśmy po jej zatrzymaniu i zinterpretować ją jako macierz przylegania G M , n . ΠMPMnKnn2GM,n
Marzio De Biasi
Dla TM , który gwarantuje, że G M , n ma Hamiltona cyklu, to chyba Π M nie jest P . MGM,nΠMP
Mohammad Al-Turkistany
@ MohammadAl-Turkistany: Myślę, że to nieprawda: wybierz TM, która po prostu buduje cykl węzłów: dla wszystkich n wykres referencyjny - który ma cykl hamiltonowski - jest łatwy do sprawdzenia w czasie wielomianowym. Mam na myśli nietrywialny przykład (raczej prostego) generatora, dla którego wydaje się trudne do wykazania, że ​​problem dotyczy P ; ale chcę zrobić kilka testów z nauty przed dodaniem go do pytania. nnP
Marzio De Biasi
1
Co z GI „Itsy Bitsy”, gdzie dla ustalonego M i N musimy zdecydować, czy dwa wykresy wygenerowane na 1 ^ n są takie same? (To jest język jednoargumentowy.)
domotorp

Odpowiedzi:

6

[To więcej niż kilka rozszerzonych komentarzy niż odpowiedzi.]

1) Jeśli , to nie ma żadnego stałego wielomianu związanego ze złożonością czasową wszystkich Π M , nawet dla M, które zajmują tylko czas, powiedzmy, n 3 : Jeśli przez cały czas - n 3 M , Π MD T I M E ( n k ) , to poniżej jest algorytm wieloczasowy dla GI. Na wejściu ( G , H ) zbuduj maszynę Turinga M G z zegarem, który zapewni, że MGIPΠMMn3n3 MΠMDTIME(nk)(G,H)MGMGnigdy nie działa przez więcej niż kroki na wejściach o rozmiarze n , i takie, że M G ( 1 | V ( G ) | ) = G , a następnie rozwiązuje Π M G ( H ) w czasie O ( n k ) .n3nMG(1|V(G)|)=GΠMG(H)O(nk)

2) Ponieważ dla dowolnego , Π M nie jest trudniejszy niż GI, można by pomyśleć, że najlepszy wynik w stylu „ Π M wydaje się nie być w P ”, na który można liczyć, że jest to wynik kompletności GI. Wydaje mi się jednak mało prawdopodobne, aby ktokolwiek Π M.MΠMΠMPΠM byłoby GI-kompletne, dla co najmniej następujących powodów:

  • Wszystkie znane mi kompletności GI dotyczą raczej dużych klas grafów, a nie pojedynczego wykresu dla każdego rozmiaru. Nawet jeśli całkowicie zrezygnujesz z wymogu wydajności, nie znam żadnej listy wykresów takiej, która | V ( G n ) | = N (lub nawet s O l r ( n ) ) w taki sposób, że testowanie izomorfizm do G NG1,G2,|V(Gn)|=npoly(n)Gn jest GI-końca.

  • W pokrewnej uwadze większość (wszystkich?) Wyników kompletności oznaczeń geograficznych to nie tylko redukcje wielokrotne jeden, ale mają one następującą postać: istnieje funkcja , która daje instancję ( G , H ) oznaczenia GI, ( f ( G ) , f ( H ) ) jest wystąpieniem innego problemu polegającego na uzupełnieniu GI. (Są to po prostu wielomianowe morfizmy relacji równoważności lub to, co Fortnow i ja nazwaliśmy „redukcjami jądra”). Możemy łatwo pokazać bezwarunkowo, że nie ma takiej redukcji z GI do dowolnego Π M (nawet jeśli zmodyfikujesz definicję, aby umożliwićf(G,H)(f(G),f(H))ΠMMdo generowania wielu wykresów). Wskazówka: uzyskaj sprzeczność, pokazując, że każdy taki musi mieć całkowicie zawarty obraz w { G M , n } n 0 .f{GM,n}n0

3) Chociaż można zbudować oparciu o uniwersalną bazę TM, jak sugerowano w pytaniu, być może nadal można skonstruować wydajny tester, ale po prostu nieskutecznie. To znaczy, może dla każdego M , Π M jest w P / p o l y ?MMΠMP/poly

Joshua Grochow
źródło
1

Nie mam odpowiedzi na twoje pytanie, ale proponuję rozważyć bardziej ograniczoną wersję dla której możemy pokazać, że leży ona w P.ΠM

Rozważmy tylko takie rodziny wykresów, że liczba krawędzi rośnie logarytmicznie. Sformalizuję to, zmieniając sformułowanie problemu, również po to, aby sprawdzić, czy dobrze to zrozumiałem.

Niekierowany wykres z n krawędziami można opisać za pomocą n 2 - nGn długi ciąg bitów, po prostu połącz wpisy macierzy sąsiedztwaGw górnym trójkącie. Dlatego są2 n 2 - nn2n2G możliwe wykresy nanwierzchołkach. Wynika z tego, że dowolna funkcjaf:NNtaka, że0f(n)<2n2-n2n2n2nf:NN dla wszystkichnopisuje rodzinę wykresów. Dla każdej efektywnie obliczalnej takiej funkcjifdefiniujemyΠfjako GΠf0f(n)<2n2n2nfΠf

GΠfG is isomorph to the graph described by f(|V(G)|)

Dla liczby naturalnej niech b 1 ( x ) będzie liczbą 1 w jego reprezentacji binarnej. Teraz rozważmy tylko Π f dla wydajnie obliczalnych funkcji f, dla których utrzymuje, że b 1 ( f ( n ) ) O ( log n )xb1(x)Πff

b1(f(n))O(logn)
, czyli rodziny grafów, dla których liczba krawędzi rośnie tylko logarytmicznie, jak podano powyżej .

Pokazujemy, że Πf dla tej klasy funkcji znajduje się w P.

Niech będzie taką funkcją, a G będzie grafem wejściowym z n wierzchołkami. Nazwijmy f ( n ) wykresem odniesienia. Na wykresie odniesienia występują najwyżej krawędzie O ( log n ) . Zatem każde MCC (maksymalnie połączony komponent) może składać się z co najwyżej O ( log n ) wierzchołków, z których może być co najwyżej n . Zauważ, że dla dowolnej pary wykresów zawierających tylko wierzchołki O ( log n ) możemy w trywialny sposób sprawdzić izomorfizm w czasie wielomianowym wrt nfGnf(n)O(logn)O(logn)nO(logn)nponieważ możemy wypróbować wszystkie permutacje. Zatem używając chciwego algorytmu do przypisania każdemu MCC wykresu wejściowego MCC na wykresie odniesienia, możemy dowiedzieć się, czy oba wykresy są izomorficzne.

John D.
źródło
, Jeśli rozumieć również swoją , jeżeli liczba krawędzi rośnie tylko logarytmicznie WRT n następnie łatwo odpaść wyizolowanego wierzchołki i badawczych wielomianu czasie, jeżeli G jest izomorficzny wykresie odniesienia. Więc w tym ograniczonym klasy, gatunku fP . fnGΠfP
Marzio De Biasi
Rzeczywiście wydaje się to łatwiejszym argumentem niż myślałem. Uwzględnię to w mojej odpowiedzi.
John D.
Biorąc pod uwagę, że ta sama argumentacja działa ogólnie na GI, nie jest to tak naprawdę satysfakcjonujące. Wydaje mi się, że byłoby interesujące, gdyby można było poprawić górną granicę krawędzi w ustawieniu , tak że nie można już wykazać analogicznej pracy z GI w ogóle. Πf
John D.
1
Dla argumentu wykorzystującego brutalną siłę (wszystkie permutacje w każdym komponencie), myślę, że tak naprawdę każdy podłączony komponent musi mieć co najwyżej wierzchołków: ( log n ) ! jest zasadniczo ( log n ) log n = n log log n . Jednak stosując najbardziej znany algorytm GI, który wymaga czasu 2 O(logn/loglogn)(logn)!(logn)logn=nloglogn , możesz zamienićO(logn/loglogn)naO(log2n). 2vlogvO(logn/loglogn)O(log2n)
Joshua Grochow