Opisuję podejście do izomorfizmu grafowego, które prawdopodobnie ma fałszywie dodatnie, i jestem ciekawy, czy istnieje literatura wskazująca, że to nie działa.
Biorąc pod uwagę dwa przylegania macierzy , co prawda naiwne Sposób sprawdzania izomorfizmie jest sprawdzenie, czy dla każdego rzędu U z G , znajduje się wiersz V z G , która jest permutacją rzędu u , oznaczony przez G [ u ] ~ H [ v ] . Nieco bardziej rygorystyczne jest pytanie, czy występuje „lokalny izomorfizm” π, dla którego G [ u ] ∼ H [ π ( u ) ]dla wszystkich wierszy. Wytwarzanie lokalnego izomorfizmu można przeprowadzić w czasie wielomianowym, budując macierz A z A [ u , v ] = ( G [ u ] ∼ H [ v ] ) ; wówczas G i H są lokalnie izomorficzne iff A ma pokrycie cyklu, a każde pokrycie cyklu jest lokalnym izomorfizmem.
Wszystkie zwykłe wykresy oszukują tę metodę, więc nieco mniej naiwne podejście polega na obliczeniu mocy macierzy i sprawdzeniu ich pod kątem lokalnego izomorfizmu, wykorzystując fakt, że masz wiele macierzy ustawiając A [ u , v ] = 0 , gdy można znaleźć żadnej siły w taki sposób, G K [ U ] ≁ H K [ V ]i sprawdzanie pokrycia cyklu tylko na końcu. Jeszcze mniej naiwnym podejściem jest znalezienie zestawu wielomianów, a nawet zestawu obwodów arytmetycznych, i ustawienie gdy znajdziemy dowolny wielomian p z p ( G ) [ u ] ≁ p ( H ) [ v ] .
Wygląda mi to na niezwykle naiwne podejście do izomorfizmu grafów, więc jestem pewien, że ktoś już to zbadał i udowodnił takie twierdzenie, jak:
Thm Dla nieskończenie wielu macierzy nieizomorficznych n × n macierzy G , H i permutacji π takie, że dla każdego wielomianu p , p ( G ) i p ( H ) są lokalnie izomorficzne według tej permutacji: p ( G ) π ∼ p ( H ) .
Pytanie: Czy istnieje takie twierdzenie? Zajrzałem do literatury i nie mogę jej znaleźć.
Jeżeli istnieje ograniczenie na stopni , która jest wielomian n taki sposób, że na każde dwa nonisomorphic matryc lokalny Izomorfizm jest potwierdzona przez obliczenie G 1 , H, 1 , ... , G s O l r ( n ) , H s O l r ( n ) lub jeśli istnieje łatwo obliczalna rodzina wielomianów p 1 , … , p k , z których każda ma długość wielomianową, ale prawdopodobnie stopień wykładniczy, wówczas mamy Palgorytm dla izomorfizmu grafów. Jeśli takie wielomiany (lub obwody arytmetyczne) są łatwe do odgadnięcia, mamy algorytm coRP . Jeśli zawsze istnieje (rodzina) obwodów arytmetycznych do obserwowania nielokalnego izomorfizmu, daje to algorytm coNP .
Zauważ, że możemy uniknąć problemu, że zapisy macierzy dużej mocy rosną zbyt duże, obliczając wielomiany na małych polach, np. Obliczając je modulo małe liczby pierwsze. W algorytmie CoNP , prover może zapewnić te liczby pierwsze.
źródło