Czy istnieje wynik wzmocnienia typu gap dla problemu Isomorphism Graph?

53

Załóżmy, że i G 2 to dwa niekierowane wykresy na zbiorze wierzchołków { 1 , … , n } . Wykresy są izomorficzne wtedy i tylko wtedy, gdy występuje permutacja Π taka, że G 1 = Π ( G 2 ) lub bardziej formalnie, jeśli istnieje permutacja Π taka, że ( i , j ) jest krawędzią w G 1 wtedy i tylko if ( Π ( i ) , Π ( jG1G2{1,…,n}ΠG1=Π(G2)Π(i,j)G1 jest krawędzią w G 2 . Problem izomorfizmu grafów polega na podejmowaniu decyzji, czy dwa dane wykresy są izomorficzne.(Π(i),Π(j))G2

Czy istnieje operacja na wykresach, która powoduje „wzmocnienie przerwy” w stylu dowodu Dinura na twierdzenie PCP ? Innymi słowy, czy istnieje transformacja obliczalna w czasie wielomianowym z do ( G ′ 1 , G ′ 2 ), tak że(G1,G2)(G1′,G2′)

  • jeśli i G 2 są izomorficzne, wówczas G ′ 1 i G ′ 2 są również izomorficzne, iG1G2G1′G2′
  • jeśli i G 2 nie są izomorficzne, to dla każdej permutacji Π wykres G ′ 1 oznacza „ ϵ -far” z Π ( G ′ 2 ) dla pewnej małej stałej ϵ , gdzie ϵ -far oznacza, że ​​jeśli wybierzemy ( i , j ) równomiernie losowo, a następnie z prawdopodobieństwem ϵ albo G1G2ΠG1′ϵΠ(G2′)ϵϵ(i,j)ϵ
    • jest krawędzią G ′ 1, a ( Π ( i ) , Π ( j ) ) nie jest krawędzią G ′ 2 , lub(i,j)G1′(Π(i),Π(j))G2′
    • nie jest krawędzią G ′ 1, a ( Π ( i ) , Π ( j ) ) jest krawędzią G ′ 2 .(i,j)G1′(Π(i),Π(j))G2′
cc.complexity-theory graph-isomorphism pcp Andre Chailloux
źródło
5
@domotorp: „Transformacja w czasie wielomianowym” to standardowa terminologia odnosząca się do deterministycznej wielomianowej maszyny Turinga, której wejście i wyjście są ciągami. W tym przypadku ta maszyna Turinga przyjmuje parę (G1, G2) jako dane wejściowe i wytwarza parę (G′1, G′2) jako dane wyjściowe. Każdy wykres jest na przykład kodowany jako sąsiednia macierz.
Tsuyoshi Ito,
1
Myślałem, że twierdzenie PCP jest ważne dla każdego problemu NP, więc w szczególności powinno to dotyczyć Graph Isomorphism?
Denis,
2
@dkuper Autor chce zapytać, czy występuje redukcja wzmacniająca przerwę, która redukuje przypadki izomorfizmu grafu do przypadków izomorfizmu grafu z większą przerwą; nie pyta bezpośrednio o twierdzenie PCP, tylko o technikę zastosowaną do udowodnienia twardości przybliżenia ...
argentpepper
3
Prawdopodobnie długa szansa, ale czy mógłbyś pokazać, że gdyby tak było, to możesz rozwiązać izomorfizm grafów w kwantowym czasie wielomianowym?
Neal Young,
3
Jest to zgodne z obecnym stanem wiedzy, że nawet SAT ma liniowy algorytm czasu, więc to, co napisałeś, wydaje się mało prawdopodobne. Jeśli tak, proszę dodać odniesienie do swojej odpowiedzi.
Kaveh

Odpowiedzi:

2

Nie wiem, czy coś takiego mogłoby istnieć, czy nie. Warto jednak zauważyć (i być może na czas), że taka „amplifikacja przerwy” prawdopodobnie implikuje quasipolynomalny algorytm czasowy dla izomorfizmu grafowego (inny niż ostatnio ogłoszony)

W tym artykule podano algorytm aproksymacji dla problemu „MAX-PGI” maksymalizacji dopasowanych par krawędzi / nie-krawędzi; jeśli zmniejszymy z GI do „Gap-MAX-PGI”, możemy w przybliżeniu rozróżnić, po której stronie luki jesteśmy.

Myślę więc, że dowód Dinura na twierdzenie PCP raczej nie da się bezpośrednio uogólnić na taki „wzmacniacz szczelinowy”, biorąc pod uwagę przeszkody, które należałoby pokonać.

Joe Bebel
źródło