22

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.

Community
  • 1
Mitch
  • 905
  • 8
  • 19
  • 2
    "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: http://en.wikipedia.org/wiki/Graph_isomorphism_problem – Aaron Sterling Aug 31 '11 at 21:33
  • 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. – 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
  • @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 Aug 31 '11 at 21:56
  • @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 Aug 31 '11 at 22:00
  • @Aaron: That is certainly nice to know, but it is about easiness of Graph Isomorphism is, not hardness. – Tsuyoshi Ito Aug 31 '11 at 22:03
  • @Tsuyoshi: I know! I was commenting, not answering. :) – Aaron Sterling Aug 31 '11 at 22:05
  • @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 Aug 31 '11 at 22:14
  • @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 Aug 31 '11 at 22:19
  • @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 Aug 31 '11 at 22:32
  • 6
    For planar graphs its known to be complete for L... See http://theorie.informatik.uni-ulm.de/Personen/toran/beatcs/column97.pdf – Joshua Herman Sep 01 '11 at 01:30
  • @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 Sep 01 '11 at 14:24
  • 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 Sep 01 '11 at 14:29
  • @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. – Aaron Sterling Sep 01 '11 at 15:31
  • @Mitch: So the "classical" result is that GI is $\Sigma_2$-low. SPP (defined here) 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 Sep 01 '11 at 15:37

1 Answers1

23

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.

Mateus de Oliveira Oliveira
  • 3,052
  • 21
  • 27