Inspired by the question is 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)

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.

  • 2
    $\begingroup$ "it was not answered at a similar sounding question" Really? I think Joshua Grochow's answer there answers the question here. $\endgroup$ Commented Aug 31, 2011 at 21:30
  • $\begingroup$ Look at the "Complexity Class GI" section here: en.wikipedia.org/wiki/Graph_isomorphism_problem $\endgroup$ Commented Aug 31, 2011 at 21:33
  • 3
    $\begingroup$ @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. $\endgroup$ Commented Aug 31, 2011 at 21:52
  • $\begingroup$ 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. $\endgroup$ Commented Aug 31, 2011 at 21:56
  • 6
    $\begingroup$ For planar graphs its known to be complete for L... See theorie.informatik.uni-ulm.de/Personen/toran/beatcs/… $\endgroup$ Commented Sep 1, 2011 at 1:30

1 Answer 1


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.

  • $\begingroup$ excellent reference (and with extra eye strain on their page, seems to be circa 2004). $\endgroup$
    – Mitch
    Commented Sep 1, 2011 at 13:59
  • $\begingroup$ Indeed, this is a nice paper. $\endgroup$ Commented Sep 1, 2011 at 20:41

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.