22
$\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.

Improve this question
$\endgroup$
16
  • 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, 2011 at 21:30
  • $\begingroup$ Look at the "Complexity Class GI" section here: en.wikipedia.org/wiki/Graph_isomorphism_problem $\endgroup$
    – Aaron Sterling
    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$
    – Tsuyoshi Ito
    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$
    – Aaron Sterling
    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$
    – Joshua Herman
    Sep 1, 2011 at 1:30

1 Answer 1

Reset to default
23
$\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.

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

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

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