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.
Możemy zdefiniować problem :
(„Małe” GI): Biorąc pod uwagę wykres , oznacza izomorficzny na ?
Innymi słowy musimy porównać dany wykres z „odniesienia” wykresie tej samej wielkości generowanej przez stałej wielomian czasu maszyna Turinga .
Dla wszystkich czasie wielomianowym maszyny Turinga , mamy , a dla wielu z nich mamy .
Ale czy to prawda dla wszystkich ? Czy problem jest znany?
Na pierwszy rzut oka myślałem, że każdy powinien być znacznie łatwiejszy niż , ponieważ dla każdego istnieje tylko jeden wykres „odniesienia” o tej wielkości i być może symetrie / asymetrie wykresów generowanych przez mogą być wykorzystane i można zbudować wydajny tester izomorfizmów ad-hoc ... ale to nieprawda: może zawierać pewnego rodzaju uniwersalną maszynę Turinga o wielomianach czasowych, która wykorzystuje (jednoargumentowy) sygnał wejściowy do generowania zupełnie innych (w strukturze) wykresów referencyjnych jako wzrasta.
źródło
Odpowiedzi:
[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 , Π M ∈ D 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 MGI∉P ΠM M n3 n3 M ΠM∈DTIME(nk) (G,H) MG MG nigdy 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 ) .n3 n MG(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 ΠM P Π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)|=n poly(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)) ΠM M do 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}n≥0
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 ?M M ΠM P/poly
źródło
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 - nG n długi ciąg bitów, po prostu połącz wpisy macierzy sąsiedztwaGw górnym trójkącie. Dlatego są2 n 2 - nn2−n2 G możliwe wykresy nanwierzchołkach. Wynika z tego, że dowolna funkcjaf:N→Ntaka, że0≤f(n)<2n2-n2n2−n2 n f:N→N dla wszystkichnopisuje rodzinę wykresów. Dla każdej efektywnie obliczalnej takiej funkcjifdefiniujemyΠfjako
G∈Πf0≤f(n)<2n2−n2 n f Πf
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 )x b1(x) Πf f
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 nf G n f(n) O(logn) O(logn) n O(logn) n ponieważ 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.
źródło