<p>Graph Isomorphism is hard for DET, the class of problems which are $NC^1$ reducible to the determinant. See "On the Hardness of Graph Isomorphism" by Jacobo Toran. <a href="http://epubs.siam.org/sicomp/resource/1/smjcat/v33/i5/p1093_s1?isAuthorized=no">http://epubs.siam.org/sicomp/resource/1/smjcat/v33/i5/p1093_s1?isAuthorized=no</a></p>

<p>It seems this is the strongest hardness result to date.</p>

CC BY-SA 3.0
2011-09-01T13:59:41.290Z
excellent reference (and with extra eye strain on their page, seems to be circa 2004).
Mitch
CC BY-SA 3.0
2011-09-01T20:41:06.173Z
Indeed, this is a nice paper.
Mateus de Oliveira Oliveira
CC BY-SA 3.0
2011-09-01T07:36:06.973Z
2011-09-01T07:36:06.973Z
Mateus de Oliveira Oliveira
<p>Inspired by the question <a href="https://cstheory.stackexchange.com/questions/8000/are-the-problems-primes-factoring-known-to-be-p-hard">is factoring known to be P-hard</a>, I wonder what the current similar state of knowledge is about the hardness of graph isomorphism. I am sure that it is currently not known if GI is in P, but:</p>

<blockquote>
  <p>what is the currently known largest class that GI is harder than?</p>
</blockquote>

<p>(it was not answered at a <a href="https://cstheory.stackexchange.com/questions/539/what-are-known-bounds-on-complexity-of-nontrivial-graph-automorphism">similar sounding question</a>)</p>

<p>To address some of the comments, I want to know the currently known maximal class(es) that GI, the problem is complete for. Known algorithms for GI are upper-bounded by superpolynomial functions, and it is a member of NP. But it is not known that GI is P-hard. I'd like to know any classes C for which it -is- known it is C-hard, and hopefully as inclusive as possible.</p>

CC BY-SA 3.0
2011-09-01T14:24:51.813Z
@Aaron: what does being 'low for SPP' mean (with respect to where GI lies in the rest of the hierarchy)? (I vaguely recall the diagram from the Toran GI book, but that's about it).
Mitch
CC BY-SA 3.0
2011-09-01T14:29:48.097Z
As to the difficulties with lower vs upper bound, it's confusing because, upper bounds are easy (give an algorithm), lower bounds are hard (hard to prove you -can't- do something. And though complexity classes and algorithms are 'about' the same thing, they mix up what you can know and what -is- known. GI is -expected- to be in a class strictly between P and NP (because it is not known to be NP-complete but is in NP and has a superpoly algorithm. But this is just an expectation, not definitive.
Mitch
CC BY-SA 3.0
2011-09-01T15:31:59.527Z
@Mitch: Informally, if a set is low for a complexity class, then it does not have any helpful information to provide that class.  Formally, $S$ is low for $\mathcal{C}$ if $\mathcal{C}$ does not grow any stronger if it has access to an $S$-oracle.  This induces a *lowness hierarchy* from P to NP, which helps measure "how close to NP-complete" a set (thought to be) in NP-P is.  For more, see [this intro](http://delivery.acm.org/10.1145/160000/156064/p10-hemaspaandra.pdf?ip=129.105.15.194&CFID=40337483&CFTOKEN=21079274&__acm__=1314891021_d98f113fe037846a7f85bbe3a9aaf384).
Aaron Sterling
CC BY-SA 3.0
2011-09-01T15:37:54.623Z
@Mitch: So the "classical" result is that GI is $\Sigma_2$-low.  SPP (defined [here](http://qwiki.stanford.edu/index.php/Complexity_Zoo:S#spp)) contains many "black box testing" problems, including GI.  I haven't read the paper by Arvind and Kurur which shows GI is low for SPP, and I can't speak to the proof. At a high level, what I understand from this fact (that GI is low for SPP) is that even if we know how to solve GI "for free," that doesn't help much if we want to test for other useful properties of an object, especially algebraic properties. Others can help you better, I am sure.
Aaron Sterling
CC BY-SA 3.0
2011-08-31T21:30:33.517Z
"it was not answered at a similar sounding question" Really? I think Joshua Grochow's answer there answers the question here.
Tyson Williams
CC BY-SA 3.0
2011-08-31T21:33:35.560Z
Look at the "Complexity Class GI" section here: http://en.wikipedia.org/wiki/Graph_isomorphism_problem
Aaron Sterling
CC BY-SA 3.0
2011-08-31T21:52:56.227Z
@Tyson and whoever up-voted his comment: I think that what Mitch is saying is that the answer there only gives upper bounds on Graph Isomorphism, not hardness of Graph Isomorphism.
Tsuyoshi Ito
CC BY-SA 3.0
2011-08-31T21:56:01.687Z
I would like to add that I don't see this as a duplicate question. Joshua's answer gives upper bounds. This question sounds more like, "Is GI at least AC0 hard?" -- yes, agree with @Tsuyoshi.
Aaron Sterling
CC BY-SA 3.0
2011-08-31T21:56:48.630Z
@Aaron: How does the Wikipedia article help in the context of the current question?  Note that the class GI in the Wikipedia article is defined as the class of problems which is polynomial-time Turing-reducible to Graph Isomorphism; the trivial fact that GI contains P does not tell anything about hardness of the Graph Isomorphism problem.
Tsuyoshi Ito
CC BY-SA 3.0
2011-08-31T22:00:26.537Z
@Tsuyoshi: it gives references for GI being low for SPP, etc., so there is more info than in Joshua's answer to the other question.
Aaron Sterling
CC BY-SA 3.0
2011-08-31T22:03:12.493Z
@Aaron: That is certainly nice to know, but it is about easiness of Graph Isomorphism is, not hardness.
Tsuyoshi Ito
CC BY-SA 3.0
2011-08-31T22:05:48.700Z
@Tsuyoshi: I know! I was commenting, not answering. :)
Aaron Sterling
CC BY-SA 3.0
2011-08-31T22:14:43.870Z
@Aaron: You may know it, but your first comment was confusing to me.  Because you posted it as a comment to this question, I naturally expected that the stated section would contain some information about hardness of Graph Isomorphism, but actually it does not contain any information about hardness of Graph Isomorphism (unless I overlooked it).  It would have been more helpful if you had specified how relevant the stated section of the linked page is to the current question in your comment, instead of just saying “look at this.”
Tsuyoshi Ito
CC BY-SA 3.0
2011-08-31T22:19:30.450Z
@Tsuyoshi: The answer to this question is not there, but there is a list of problems that are GI-hard, and others that are contained in GI. That seemed to be in the spirit of the question, which was what do we know about the exqct hardness of GI. The aggressive comment above mine was not visible to me when I posted, or I might have used more words. I am sorry for being confusing.
Aaron Sterling
CC BY-SA 3.0
2011-08-31T22:32:24.347Z
@Aaron: I had not noticed that your comment and Tyson’s comment had been posted at almost the same time.  That explains why you had posted a comment which I thought was incredibly confusing.  Thanks for the explanation, and sorry for being harsh.  (But still: next time, please consider adding some context rather than posting just a link.  Some people post an answer as a comment, especially if it consists of a single link, and I thought that your comment was of this kind.)
Tsuyoshi Ito
CC BY-SA 3.0
2011-09-01T01:30:33.717Z
For planar graphs its known to be complete for L... See http://theorie.informatik.uni-ulm.de/Personen/toran/beatcs/column97.pdf
Joshua Herman
<cc.complexity-theory><complexity-classes><graph-isomorphism>
What is the current known hardness of Graph Isomorphism?
Mitch
# What is the current known hardness of Graph Isomorphism?

(Asked by: username_0 on 2011-08-31)

Inspired by the question [is factoring known to be P-hard](https://cstheory.stackexchange.com/questions/8000/are-the-problems-primes-factoring-known-to-be-p-hard), I wonder what the current similar state of knowledge is about the hardness of graph isomorphism. I am sure that it is currently not known if GI is in P, but:

> what is the currently known largest class that GI is harder than?

(it was not answered at a [similar sounding question](https://cstheory.stackexchange.com/questions/539/what-are-known-bounds-on-complexity-of-nontrivial-graph-automorphism))

To address some of the comments, I want to know the currently known maximal class(es) that GI, the problem is complete for. Known algorithms for GI are upper-bounded by superpolynomial functions, and it is a member of NP. But it is not known that GI is P-hard. I'd like to know any classes C for which it -is- known it is C-hard, and hopefully as inclusive as possible.

**Tags:** cc.complexity-theory, complexity-classes, graph-isomorphism
> **Comments:**
> **username_2**: "it was not answered at a similar sounding question" Really? I think Joshua Grochow's answer there answers the question here.  
> **username_1**: Look at the "Complexity Class GI" section here: http://en.wikipedia.org/wiki/Graph_isomorphism_problem  
> **username_3**: @Tyson and whoever up-voted his comment: I think that what Mitch is saying is that the answer there only gives upper bounds on Graph Isomorphism, not hardness of Graph Isomorphism.  
> **username_1**: I would like to add that I don't see this as a duplicate question. Joshua's answer gives upper bounds. This question sounds more like, "Is GI at least AC0 hard?" -- yes, agree with @Tsuyoshi.  
> **username_3**: @Aaron: How does the Wikipedia article help in the context of the current question?  Note that the class GI in the Wikipedia article is defined as the class of problems which is polynomial-time Turing-reducible to Graph Isomorphism; the trivial fact that GI contains P does not tell anything about hardness of the Graph Isomorphism problem.  
> **username_1**: @Tsuyoshi: it gives references for GI being low for SPP, etc., so there is more info than in Joshua's answer to the other question.  
> **username_3**: @Aaron: That is certainly nice to know, but it is about easiness of Graph Isomorphism is, not hardness.  
> **username_1**: @Tsuyoshi: I know! I was commenting, not answering. :)  
> **username_3**: @Aaron: You may know it, but your first comment was confusing to me.  Because you posted it as a comment to this question, I naturally expected that the stated section would contain some information about hardness of Graph Isomorphism, but actually it does not contain any information about hardness of Graph Isomorphism (unless I overlooked it).  It would have been more helpful if you had specified how relevant the stated section of the linked page is to the current question in your comment, instead of just saying “look at this.”  
> **username_1**: @Tsuyoshi: The answer to this question is not there, but there is a list of problems that are GI-hard, and others that are contained in GI. That seemed to be in the spirit of the question, which was what do we know about the exqct hardness of GI. The aggressive comment above mine was not visible to me when I posted, or I might have used more words. I am sorry for being confusing.  
> **username_3**: @Aaron: I had not noticed that your comment and Tyson’s comment had been posted at almost the same time.  That explains why you had posted a comment which I thought was incredibly confusing.  Thanks for the explanation, and sorry for being harsh.  (But still: next time, please consider adding some context rather than posting just a link.  Some people post an answer as a comment, especially if it consists of a single link, and I thought that your comment was of this kind.)  
> **username_4**: For planar graphs its known to be complete for L... See http://theorie.informatik.uni-ulm.de/Personen/toran/beatcs/column97.pdf  
> **username_0**: @Aaron: what does being 'low for SPP' mean (with respect to where GI lies in the rest of the hierarchy)? (I vaguely recall the diagram from the Toran GI book, but that's about it).  
> **username_0**: As to the difficulties with lower vs upper bound, it's confusing because, upper bounds are easy (give an algorithm), lower bounds are hard (hard to prove you -can't- do something. And though complexity classes and algorithms are 'about' the same thing, they mix up what you can know and what -is- known. GI is -expected- to be in a class strictly between P and NP (because it is not known to be NP-complete but is in NP and has a superpoly algorithm. But this is just an expectation, not definitive.  
> **username_1**: @Mitch: Informally, if a set is low for a complexity class, then it does not have any helpful information to provide that class.  Formally, $S$ is low for $\mathcal{C}$ if $\mathcal{C}$ does not grow any stronger if it has access to an $S$-oracle.  This induces a *lowness hierarchy* from P to NP, which helps measure "how close to NP-complete" a set (thought to be) in NP-P is.  For more, see [this intro](http://delivery.acm.org/10.1145/160000/156064/p10-hemaspaandra.pdf?ip=129.105.15.194&CFID=40337483&CFTOKEN=21079274&__acm__=1314891021_d98f113fe037846a7f85bbe3a9aaf384).  
> **username_1**: @Mitch: So the "classical" result is that GI is $\Sigma_2$-low.  SPP (defined [here](http://qwiki.stanford.edu/index.php/Complexity_Zoo:S#spp)) contains many "black box testing" problems, including GI.  I haven't read the paper by Arvind and Kurur which shows GI is low for SPP, and I can't speak to the proof. At a high level, what I understand from this fact (that GI is low for SPP) is that even if we know how to solve GI "for free," that doesn't help much if we want to test for other useful properties of an object, especially algebraic properties. Others can help you better, I am sure.  

---

## 1 answers

### Answer by username_5 on 2011-09-01. Score: 23 | Accepted answer

Graph Isomorphism is hard for DET, the class of problems which are $NC^1$ reducible to the determinant. See "On the Hardness of Graph Isomorphism" by Jacobo Toran. <http://epubs.siam.org/sicomp/resource/1/smjcat/v33/i5/p1093_s1?isAuthorized=no>

It seems this is the strongest hardness result to date.

> **Comments:**
> **username_0**: excellent reference (and with extra eye strain on their page, seems to be circa 2004).  
> **username_5**: Indeed, this is a nice paper.  

---

