„Mały” wykres izomorfizmu

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.$M$$1^n$$G_{M,n}$$n$

Możemy zdefiniować problem $\Pi_M$ :

(„Małe” GI): Biorąc pod uwagę wykres $G=(V,E)$ , oznacza $G$ izomorficzny na $G_{M,|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 $\Pi_M \in NP$ , a dla wielu z nich mamy $\Pi_M \in P$ .
Ale czy to prawda dla wszystkich $M$ ? Czy problem jest znany?

Na pierwszy rzut oka myślałem, że każdy $\Pi_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 $1^n$ do generowania zupełnie innych (w strukturze) wykresów referencyjnych jako $n$ wzrasta.

[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 $GI \notin \mathsf{P}$$\Pi_{M}$$M$$n^3$$n^3$ $M$$\Pi_{M} \in \mathsf{DTIME}(n^k)$$(G, H)$$M_{G}$$M_{G}$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 ) .$n^3$$n$$M_{G}(1^{|V(G)|}) = G$$\Pi_{M_G}(H)$$O(n^k)$

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$$\Pi_{M}$$\Pi_M$$\mathsf{P}$$\Pi_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 $G_1, G_2, \dotsc$$|V(G_n)| = n$$poly(n)$$G_n$ 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))$$\Pi_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$$\{G_{M,n}\}_{n \geq 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$$\Pi_{M}$$\mathsf{P/poly}$

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.$\Pi_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 - $G$$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 - $\frac{n^2-n}{2}$$G$ możliwe wykresy nanwierzchołkach. Wynika z tego, że dowolna funkcjaf:N→Ntaka, że0≤f(n)<2n2-$2^{\frac{n^2-n}{2}}$$n$$f : \mathbb{N} \rightarrow \mathbb{N}$ dla wszystkichnopisuje rodzinę wykresów. Dla każdej efektywnie obliczalnej takiej funkcjifdefiniujemyΠfjako G∈Π$0 \leq f(n) < 2^{\frac{n^2-n}{2}}$$n$$f$$\Pi_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$$b_1(x)$$\Pi_f$$f$

Pokazujemy, że $\Pi_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 $f$$G$$n$$f(n)$$\mathcal{O}(\log n)$$\mathcal{O}(\log n)$$n$$\mathcal{O}(\log n)$$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.