It is easy to see that graph isomorphism(GI) is in NP. It is a major open problem whether GI is in coNP. Are there any potential candidates of properties of graphs that can be used as coNP certificates of GI. Any conjectures that imply $GI \in coNP$ ? What are some implications of $GI \in coNP$ ?


3 Answers 3


If $GI$ is in $coNP$, then we would have the result: $GI$ is not $NP$-complete unless $NP=coNP=PH$. (Currently known: $GI$ is not $NP$-complete unless $\Sigma_2 P = \Pi_2 P = PH$).

Since $GI$ is in $coAM$, obviously derandomizing $coAM$ (doi link) would put $GI \in coNP$, but I don't know of any candidate graph properties for putting $GI \in coNP$ otherwise. I look forward to more answers though!

Interestingly, in that paper they also show that Graph Non-Isomorphism has subexponential size proofs -- that is, $GI \in co NSUBEXP$ -- unless $PH = \Sigma_3 P$. This is at least headed in the direction of showing conditionally that $GI \in coNP$.

  • 5
    $\begingroup$ There is another derandomization result for $AM \cap coAM$ by Gutfreund, Shaltiel and Ta-Shma (Uniform hardness vs. randomness for Arthur-Merlin games, in Computational Complexity 12(3-4):85-130, 2003) . This result works under uniform hardness assumptions (with the usual i.o. caveat). $\endgroup$
    – Alon Rosen
    Nov 17, 2010 at 6:07

How about the range (i.e. list, one entry per edge) of effective resistances? The effective resistance of an edge is the probability that the edge is in a random spanning tree. Effective resistances can be found using algorithms of Spielman and Teng, although I don't know how easy it is to actually implement (if one wanted to do experiments).

Suppose we have two strongly regular graphs, which have the same eigenvalues (and we know that eigenvalues do not necessarily distinguish between non-isomorphic graphs). Then if the effective resistances (i.e. the lists, again) are the same, they can not be used to distinguish the graphs. But why would two co-spectral graphs have the same distribution of their edges in random spanning trees? Is there a known connection between the graph spectrum and the effective resistances of a graph? i.e. knowning the graph spectrum, can we compute the effective resistances?


It could be interesting to point out that if GI is not in coNP then P ≠ NP.

1)If GI is not in coNp then GI ≠ NGI

2)If GI ≠ NGI then GI ≠ P

3)If GI ≠ P then P ≠ NP

As a corollary of the upon propositions we have: if GI is not in coNP then P ≠ NP. The same holds if NGI is not in NP.

  • 3
    $\begingroup$ This is kind of trivial and holds for any NP problem. $\endgroup$
    – Kaveh
    Sep 29, 2015 at 21:02

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.