<p>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). </p>

<p>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?</p>

CC BY-SA 2.5
2010-11-17T03:48:33.770Z
2010-11-17T03:48:33.770Z
asterix
<p>It could be interesting to point out that if GI is not in coNP then P ≠ NP. </p>

<p>1)If GI is not in coNp then GI ≠ NGI</p>

<p>2)If GI ≠ NGI then GI ≠ P</p>

<p>3)If GI ≠ P then P ≠ NP</p>

<p>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.</p>

CC BY-SA 3.0
2015-09-29T21:02:53.067Z
This is kind of trivial and holds for any NP problem.
Kaveh
CC BY-SA 2.5
2011-01-05T14:38:05.007Z
2011-01-05T14:38:05.007Z
Francesco Cris
<p>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$).</p>

<p>Since $GI$ is in $coAM$, obviously <a href="http://pages.cs.wisc.edu/~dieter/Research/r-gni.html">derandomizing $coAM$</a> (<a href="http://dx.doi.org/10.1137/S0097539700389652">doi link</a>) 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!</p>

<p>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$.</p>

CC BY-SA 2.5
2010-11-17T06:07:16.280Z
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).
Alon Rosen
CC BY-SA 2.5
2010-11-16T20:52:20.217Z
2010-11-16T20:52:20.217Z
Joshua Grochow
<p>It is easy to see that <a href="http://en.wikipedia.org/wiki/Graph_isomorphism_problem">graph isomorphism</a>(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$ ?</p>

<cc.complexity-theory><graph-isomorphism>
coNP certificate for Graph Isomorphism
Shiva Kintali
# coNP certificate for Graph Isomorphism

(Asked by: username_0 on 2010-11-16)

It is easy to see that [graph isomorphism](http://en.wikipedia.org/wiki/Graph_isomorphism_problem)(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$ ?

**Tags:** cc.complexity-theory, graph-isomorphism


---

## 3 answers

### Answer by username_4 on 2010-11-16. Score: 24 | Accepted answer

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$](http://pages.cs.wisc.edu/~dieter/Research/r-gni.html) ([doi link](http://dx.doi.org/10.1137/S0097539700389652)) 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$.

> **Comments:**
> **username_5**: 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).  

---

### Answer by username_1 on 2010-11-17. Score: 6

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?


---

### Answer by username_2 on 2011-01-05. Score: -1

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.

> **Comments:**
> **username_3**: This is kind of trivial and holds for any NP problem.  

---

