23
$\begingroup$

Motivated by Fortnow's comment on my post, Evidence that Graph Isomorphism problem is not $NP$-complete, and by the fact that $GI$ is a prime candidate for $NP$-intermediate problem (not $NP$-complete nor in $P$), I am interested in known evidences that $GI$ is not in $P$.

One such evidence is the $NP$-completeness of a restricted Graph Automorphism problem(fixed-point free graph automorphism problem is $NP$-complete). This problem and other generalizations of $GI$ were studied in "Some NP-complete problems similar to Graph Isomorphism" by Lubiw. Some may argue as evidence the fact that despite more than 45 years no one found polynomial-time algorithm for $GI$.

What other evidence do we have to believe that $GI$ is not in $P$?

$\endgroup$
  • 2
    $\begingroup$ Subgraph-isomorphism is also NP-complete. $\;$ $\endgroup$ – user6973 Aug 2 '15 at 15:52
  • 1
    $\begingroup$ Somewhat weak evidence is the growing class of problems that are logspace-equivalent to GI, yet none of which seems to have obvious polytime algorithms. (Of course, if one of them does have a polytime algorithm then they all do.) $\endgroup$ – András Salamon Aug 2 '15 at 22:51
  • $\begingroup$ circumstantial evidence similar to P vs NP: decades of optimization of GI algorithms eg nauty that still have experimentally verifiable non-P worst case trends, apparently mainly on random regular graphs. $\endgroup$ – vzn Aug 3 '15 at 20:29
  • 1
    $\begingroup$ see also hard graphs for GI testing $\endgroup$ – vzn Aug 4 '15 at 3:02
  • $\begingroup$ What do you think about this? dharwadker.org/tevet/isomorphism $\endgroup$ – Anna Tomskova 15 hours ago
11
$\begingroup$

Before this question, my opinion was that Graph Isomorphism might be in P, i.e. that there is no evidence to believe that GI is not in P. So I asked myself what would count as evidence for me: If there were mature algorithms for $p$-group isomorphism that fully exploited the available structure of $p$-groups and still would have no hope to achieve polynomial runtime, then I would agree that GI is probably not in P. There are known algorithms that exploit the available structure like Isomorphism testing for $p$-groups. by O'Brien (1994), but I haven't read it in sufficient detail to judge whether it fully exploits the available structure, or whether there is any hope to improve this algorithm (without exploiting additional non-obvious structure of $p$-groups) to achieve polynomial runtime.

But I knew that Dick Lipton called for action near the end of 2011 to clarify the computational complexity of the group isomorphism problem in general, and of the $p$-group isomorphism problem specifically. So I googled for

site:https://rjlipton.wordpress.com group isomorphism

in order to see whether the call for action had been successful. It was indeed:

  1. The Group Isomorphism Problem: A Possible Polymath Problem?
  2. Advances on Group Isomorphism
  3. Three From CCC: Progress on Group Isomorphism

The last post reviews a paper which achieves $n^{O(\log \log n)}$ runtime for certain important families of groups, exploits much of the available structure, and acknowledges the above mentioned paper from 1994. Because the $n^{O(\log \log n)}$ runtime bound is both compatible with the experience that graph isomorphism is not hard in practice, and with the experience that nobody is able to come up with a polynomial time algorithm (even for group isomorphism), this can be counted as evidence that GI is not in P.

$\endgroup$
  • $\begingroup$ rjlipton.wordpress.com/2015/03/05/news-on-intermediate-problems also turned up by my search. It cites Theorem 2 Graph Isomorphism is in ${\mathsf{RP}^{\mathrm{MCSP}}}$. Moreover, every promise problem in ${\mathsf{SZK}}$ belongs to ${\mathsf{BPP}^{\mathrm{MCSP}}}$ as defined for promise problems. This is evidence that GI is not NP-complete, but this wasn't the question here. Let me add that I see no problem with the length or style of my answer, because I interpret a request for evidence as a request for a reasoned opinion. $\endgroup$ – Thomas Klimpel Aug 3 '15 at 8:54
  • 5
    $\begingroup$ I don't follow your reasoning. How can you know that the "available structure" is "fully exploited"? If anything, doesn't the Grochow-Qiao paper suggest that much more can be done with cohomology classes? $\endgroup$ – Sasho Nikolov Aug 4 '15 at 4:47
  • $\begingroup$ @SashoNikolov By the "available structure", I mean the knowledge about the structure in the group theory community, related communities and existing publications. Examples were the structure is not "fully exploited" are publications whose main goal is to come up with a practical implementable algorithm, which therefore stop at some point and just mention the remaining limitations without clear indications whether those are fundamental. The Grochow-Qiao paper reviewed those and directly attacked the computational complexity of group isomorphism, hence its results provide good evidence. $\endgroup$ – Thomas Klimpel Aug 4 '15 at 7:58
11
$\begingroup$

The smallest set of permutations you have to check to verify that no non-trivial permutations exist in a black box setting is better than $n!$ but still exponential, OEIS A186202.

The number of bits needed to store an unlabeled graph is $log_{2}$ of ${n\choose 2}-n log(n) +O(n)$. See Naor, Moni. "Succinct representation of general unlabeled graphs." Discrete Applied Mathematics 28.3 (1990): 303-307. The compression method proof is a bit cleaner if I recall. Anyway, lets call that set $U$. Let $L=2^{{n\choose 2}}$ for labeled graphs.

--Haskell notation
graphCanonicalForm :: L -> U

graphIsomorphism :: L -> L -> Bool
graphIsomorphism a b = (graphCanonicalForm a) == (graphCanonicalForm b)    

$U^L$ and $Bool^{L^{L}}$ if you convert to exponentials. Just examining their type signatures putting graphs in canonical form looks easier, but as shown above GC makes GI easy.

$\endgroup$
  • $\begingroup$ Thanks. How strong is this kind of arguments? $\endgroup$ – Mohammad Al-Turkistany Aug 3 '15 at 8:50
  • $\begingroup$ is there a ref to be cited that documents this connection further? $\endgroup$ – vzn Aug 4 '15 at 3:01
  • 3
    $\begingroup$ @MohammadAl-Turkistany: This is basically a query complexity argument. But known algorithms, e.g. Babai-Luks 1983, already beat this bound, I think by quite a significant margin (something like $2^n$ versus $2^{\sqrt{n}}$). $\endgroup$ – Joshua Grochow Aug 5 '15 at 2:33
  • 1
    $\begingroup$ @ChadBrewbaker: If your concern is being coded up, and average-case complexity I'm sure that nauty does significantly better than your algorithm. (Note that the best known lower bound on nauty is $\Omega(2^{n/20})$ (Miyazaki 1996), and a poly-time algorithm was found for the Miyazaki graphs. A simple analysis shows a lower bound of $(3/2)^n$ on your algorithm.) Also, GI is in average-case linear time (Babai-Kucera). $\endgroup$ – Joshua Grochow Aug 5 '15 at 4:58
  • 2
    $\begingroup$ @MohammadAl-Turkistany: this question has made me think more deeply about my beliefs on the complexity of GI. Re: your other question, note that if there is no poly-time Turing (or even many-one) reduction from GI to GA then P$\neq$NP. $\endgroup$ – Joshua Grochow Aug 5 '15 at 22:48
8
$\begingroup$

Kozen in his paper, A clique problem equivalent to graph isomorphism, gives an evidence that $GI$ is not in $P$. The following is from the paper:

"Nevertheless, it is likely that finding a polynomial time algorithm for graph isomorphism will be as difficult as finding a polynomial time algorithm for an NP-complete problem. In support of this claim, we give a problem equivalent to graph isomorphism, a small perturbation of which is NP-complete."

Also, Babai in his recent breakthrough paper Graph Isomorphism in quasipolynomial time gives an argument against the existence of efficient algorithms for GI. He observes that the group isomorphism problem (which is reducible to GI) is a major obstacle to placing GI in $P$. Group Isomorphism problem ( groups are given by their Cayley tableis) is solvable in $n^{O(\log n)}$ and it is not known to be in $P$.

Here is an excerpt from Babai's paper:

The result of the present paper amplifies the significance of the Group Isomorphism problem (and the challenge problem stated) as a barrier to placing GI in P. It is quite possible that the intermediate status of GI (neither NP-complete, nor polynomial time) will persist.

$\endgroup$
  • 2
    $\begingroup$ From Kozen's Lem. 3 one can get a simpler example of this phenomenon: namely, Induced Subgraph Isomorphism (is $H$ an induced subgraph of $G$) is exactly GI when $|G|=|H|$, but is NP-hard when $|G|=c|H|$ for any $c > 1$. For discrete parameters, we know there are problems in P that quickly become NP-complete (e.g. 2SAT vs 3SAT). Do you know if there are examples of problems in P with some continuous parameter that become NP-complete at a sharp threshold? If so, then this kind of reasoning wouldn't be much evidence that GI isn't in P, but I can't think of such an example off the top of my head. $\endgroup$ – Joshua Grochow Aug 5 '15 at 5:25
  • 2
    $\begingroup$ @JoshuaGrochow No, I am not aware of any such decision problems. But for optimization problems I know that finding an assignment satisfying $7/8$ of the clauses is in $P$ while finding an assignment satisfying $7/8+ϵ$ of the clauses is $NP$-hard even for satisfiable 3SAT formulas ($ϵ>0$ ). $\endgroup$ – Mohammad Al-Turkistany Aug 5 '15 at 13:29
  • $\begingroup$ Oops, Klimpel's answer already contains the group isomorphism evidence. Anyway, it is useful to have Babai's perspective on the matter. $\endgroup$ – Mohammad Al-Turkistany Dec 20 '15 at 18:29
  • $\begingroup$ Babai retracted the claim of quasipolynomial runtime. Apparently there was an error in the analysis. $\endgroup$ – Raphael Jan 4 '17 at 21:55
5
$\begingroup$

here are other results not cited yet

  • On the hardness of Graph Isomorphism / Torán FOCS 2000 and SIAM J. Comput. 33, 5 1093-1108.

    We show that the graph isomorphism problem is hard under DLOGTIME uniform AC0 many-one reductions for the complexity classes NL, PL (probabilistic logarithmic space) for every logarithmic space modular class ModkL and for the class DET of problems NC1 reducible to the determinant. These are the strongest known hardness results for the graph isomorphism problem and imply a randomized logarithmic space reduction from the perfect matching problem to graph isomorphism. We also investigate hardness results for the graph automorphism problem.

  • Graph Isomorphism is not AC0 reducible to Group Isomorphism / Chattopadhyay, Toran, Wagner

    We give a new upper bound for the Group and Quasigroup Isomorphism problems when the input structures are given explicitly by multiplication tables. We show that these problems can be computed by polynomial size nondeterministic circuits of unbounded fan-in with O(log log n) depth and O(log2 n) nondeterministic bits, where n is the number of group elements. This improves the existing upper bound from [Wol94] for the problems. In the previous upper bound the circuits have bounded fanin but depth O(log2 n) and also O(log2 n) nondeterministic bits. We then prove that the kind of circuits from our upper bound cannot compute the Parity function. Since Parity is AC0 reducible to Graph Isomorphism, this implies that Graph Isomorphism is strictly harder than Group or Quasigroup Isomorphism under the ordering defined by AC0 reductions.

$\endgroup$
  • 4
    $\begingroup$ Although these are indeed the strongest known lower bounds on GI, they don't really say anything about its not being in P. In the first case, DET isn't so close to P. In the second case, note that the structure of the $\mathsf{AC}^0$-degrees within P is already quite rich. $\endgroup$ – Joshua Grochow Aug 5 '15 at 5:07
  • $\begingroup$ re "strongest known lower bounds on GI", ofc GI is in NP so an actual proof that GI is not in P is equivalent to P≠NP! (possibly via NPI≠∅)... $\endgroup$ – vzn Aug 5 '15 at 14:55
  • 4
    $\begingroup$ Yes, but, for example, it would be nice to know that GI is P-hard! (Of course, P-hardness has very little to do with showing that something is not in P, but it would at least suggest that GI is not in NC!) $\endgroup$ – Joshua Grochow Aug 5 '15 at 21:13

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.