Certyfikat CoNP dla Graph Isomorphism

29

Łatwo zauważyć, że izomorfizm wykresu (GI) występuje w NP. Poważnym otwartym problemem jest to, czy GI jest w CoNP. Czy są potencjalni kandydaci właściwości grafów, które można wykorzystać jako certyfikaty CoNP dla GI? Jakieś przypuszczenia, które sugerują, że ? Jakie są implikacje ? $GI \in coNP$ $GI \in coNP$

cc.complexity-theory graph-isomorphism

— Shiva Kintali
źródło

21

Jeśli jest w , otrzymalibyśmy wynik: nie jest -kompletny, chyba że . (Obecnie znane: nie jest chyba że ). $GI$ $coNP$ $GI$ $NP$ $NP=coNP=PH$ $GI$ $NP$ $\Sigma_2 P = \Pi_2 P = PH$

Ponieważ jest w , oczywiście derandomizacja ( link doi ) umieściłaby , ale nie znam żadnych właściwości grafów kandydujących do umieszczenia inny sposób. Czekam na więcej odpowiedzi! $GI$ $coAM$ $coAM$ $GI \in coNP$ $GI \in coNP$

Co interesujące, w tej pracy pokazują, że wykres dla Izomorfizm ma subexponential dowody wielkości - czyli - o ile . To przynajmniej zmierza w kierunku warunkowego pokazania, że . $GI \in co NSUBEXP$ $PH = \Sigma_3 P$ $GI \in coNP$

— Joshua Grochow
źródło

5

Istnieje inny wynik derandomizacji dla autorstwa Gutfreunda, Shaltiela i Ta-Shmy (Jednorodna twardość vs. losowość w grach Arthur-Merlin, w Computational Complexity 12 (3-4): 85-130, 2003). Ten wynik działa przy jednolitych założeniach twardości (ze zwykłym zastrzeżeniem io).

A M \cap c o A M

$AM \cap coAM$

— Alon Rosen,

5

A co z zakresem (tj. Listą, jednym wpisem na krawędź) efektywnych rezystancji? Efektywny opór krawędzi to prawdopodobieństwo, że krawędź znajduje się w przypadkowym drzewie rozpinającym. Efektywne opory można znaleźć za pomocą algorytmów Spielmana i Tenga, chociaż nie wiem, jak łatwo jest to faktycznie zaimplementować (jeśli ktoś chciałby eksperymentować).

Załóżmy, że mamy dwa bardzo regularne wykresy, które mają te same wartości własne (i wiemy, że wartości własne niekoniecznie rozróżniają grafy nieizomorficzne). Następnie, jeśli rezystancje efektywne (tj. Znowu listy) są takie same, nie można ich użyć do rozróżnienia wykresów. Ale dlaczego dwa wykresy współspektralne miałyby taki sam rozkład ich krawędzi w losowo rosnących drzewach? Czy istnieje znany związek między widmem wykresu a efektywnymi rezystancjami wykresu? tzn. znając spektrum wykresów, czy możemy obliczyć efektywne rezystancje?

— gwiazdka
źródło

-1

Interesujące może być wskazanie, że jeśli GI nie znajduje się w CoNP, to P ≠ NP.

1) Jeśli GI nie jest w CoNp, to GI ≠ NGI

2) Jeżeli GI ≠ NGI, to GI ≠ P

3) Jeżeli GI ≠ P, to P ≠ NP

Jako następstwo powyższych twierdzeń mamy: jeśli GI nie znajduje się w coNP, to P ≠ NP. To samo dotyczy sytuacji, gdy NGI nie ma w NP.

— Francesco Cris
źródło

1

Jest to trochę banalne i dotyczy każdego problemu NP.

— Kaveh