G-trudnym problemem wykres nie wiadomo, że

Wykres Izomorfizm ( ) jest dobrym kandydatem dla problemu -intermediate. istnieje -intermediate problemy chyba . Szukam naturalnego problemu, który jest trudny dla przy redukcji Karp (Problem graficzny taki, że ). $GI$ $NP$ $NP$ $P=NP$ $GI$ $X$ $GI <_p^m X$

Czy istnieje naturalna -hard wykres problem, który nie jest ani -equivalent ani znany jako $GI$ $GI$ -Complete? $NP$

— Mohammad Al-Turkistany
źródło

Ekwiwalent GI w ramach redukcji Karp.

— Mohammad Al-Turkistany,

kandydatów: problemy między P i NPC

— vzn

Wydaje się, że możliwe jest zbudowanie nieskończonej hierarchii takich problemów, łącząc „wystarczającą ilość” Kliki z GI, w wariancie opóźnionej diagonalizacji. Zobacz także podobną konstrukcję sugerowaną przez Bodirsky / Chen / Grohe / Thurley / Weyer.

— András Salamon,

Nawiasem mówiąc, możesz zmienić tytuł na „Problem z grafem trudnym dla GI, o którym wiadomo, że nie jest NP-zupełny”. Moją pierwszą myślą, kiedy zobaczyłem obecny tytuł, było „Ring Isomorphism!” ale odpowiedź, którą znalazłeś, jest (myślę) znacznie bardziej interesująca.

— Joshua Grochow

@JoshuaGrochow Dziękujemy za opinię. Co sugerujesz? Zauważ, że interesują mnie problemy z wykresem.

— Mohammad Al-Turkistany

Odpowiedzi:

Po obszernych poszukiwaniach znalazłem uzasadniony problem z wierzchołkiem wierzchołka (LVD), który jest związany ze słynną hipotezą Rekonstrukcji Grafu . Pomost grafu to wielu zestaw wykresów tak, że jest izomorficzny ( przedstawia wykres uzyskano z $G(V, E)$ $F = \{G_1,G_2, . . . , G_n\}$ $G_i$ $G−v_i$ $G-v$ $G$ usuwając $v$ i jego krawędzie incydentów). ( ) $|V|=n$

Problem VERTEX-SUBDECK k uzasadnione, biorąc pod uwagę wiele zestaw wykresów zdecydować, czy jest wykresem , tak że jest podzbiorem wierzchołek pokładu ( k LVD = $F= \{G_1,G_2, . . . , G_k\}$ $G$ $F$ ) gdzie $\{[G_1, . . . , G_k]|(∃G)[[G_1, . . . , G_k] ⊆ vertex-deck(G)]\}$ $k \ge 3$

Problem k-LVD to twardy i nie jest znany jako równoważny. Jest otwarty problem, czy K-LVD jest -Complete (dla ). Zobacz sekcję „Otwarte problemy” złożoności wyników w rekonstrukcji wykresu . $GI$ $GI$ $NP$ $k \ge 3$

Ponadto artykuł sugeruje istnienie problemu pośredniej złożoności między i k-LVD . Problemem jest to, LVD = n-LVD którym wszystkie podano karty kandydujące (wejście LVD jest . $GI$ $n$ $F= \{G_1,G_2, . . . , G_n \})$

— Mohammad Al-Turkistany
źródło

$G_1$ $G_2$ $n$ $pi$ $G_1$ $G_2$