Uważam, że odpowiedź na twoje pytanie brzmi „nie”, ponieważ równoważny warunek oznaczałby wielomianowe rozwiązanie GI.
W przypadku macierz przyległości wykresu należy zauważyć, że liczba ścieżek od do długości wynosi (przy dozwolonym powtórzeniu wierzchołków i krawędzi). Na dwóch wykresach i (z sąsiedztwa macierzy i ) i , gdy sortowane elementy i , a następnie w celu bycia izomorficzna jest to konieczny warunek, że listy są identyczne dla wszystkich .G i j k ( A k ) i , j G 1 G 2 A 1 A 2 k ≥ 1 A k 1 A k 2 G 1 G 2 kZAsoljajotk(Ak)i,jG1G2A1A2k≥1Ak1Ak2G1G2k
Uważam, że twoje przypuszczenie jest równoważne z:
Jeżeli sortowane wykaz elementów i są identyczne dla do (górna granica w najdłuższej ścieżce z wierzchołków niepowtarzającego), a następnie i są izomorficzne. A d 2 k = 1 n - 1 G 1 G 2Ak1Ad2k=1n−1G1G2
Aby rozwiązać GI, wystarczy wykonać mnożenia macierzy (i trochę więcej czasu na sortowanie i porównywanie elementów). Zajmie to mniej niż czasu.n × n n 2 n 4n−1n×nn2n4
Przyznaję dwie możliwe wady w mojej argumentacji. Po pierwsze, jest całkowicie możliwe, że GI ma algorytm wielomianowy i że właśnie go odkryliśmy, właśnie teraz (brawo, jesteśmy sławni!). Uważam to za bardzo mało prawdopodobne. Po drugie (i o wiele bardziej prawdopodobne) to, co zaproponowałem, nie jest w rzeczywistości równoznaczne z twoją hipotezą.
Końcowa myśl. Czy wypróbowałeś to dla wszystkich, powiedzmy, 3-regularnych wykresów dla rozmiaru około 8? Sądzę, że jeśli twoje przypuszczenie jest fałszywe, powinien istnieć przeciwny przykład na 3-regularnych wykresach o dość małym rozmiarze.