Certyfikat CoNP dla Graph Isomorphism

Ł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$

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$

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?

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.