# What is the current known hardness of Graph Isomorphism?

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.

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

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.

• excellent reference (and with extra eye strain on their page, seems to be circa 2004). – Mitch Sep 1 '11 at 13:59
• Indeed, this is a nice paper. – Mateus de Oliveira Oliveira Sep 1 '11 at 20:41