21
$\begingroup$

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.

$\endgroup$
  • 2
    $\begingroup$ "it was not answered at a similar sounding question" Really? I think Joshua Grochow's answer there answers the question here. $\endgroup$ – Tyson Williams Aug 31 '11 at 21:30
  • $\begingroup$ Look at the "Complexity Class GI" section here: en.wikipedia.org/wiki/Graph_isomorphism_problem $\endgroup$ – Aaron Sterling Aug 31 '11 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$ – Tsuyoshi Ito Aug 31 '11 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$ – Aaron Sterling Aug 31 '11 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$ – Joshua Herman Sep 1 '11 at 1:30
22
$\begingroup$

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.

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

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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