Graph isomorphism problem is one of the longest standing problems that resisted classification into $P$ or $NP$-complete problems. We have evidences that it can not be $NP$-complete. Firstly, Graph Isomorphism can not be $NP$-complete unless the polynomial hierarchy [1] collapses to the second level. Also, the counting[2] version of GI is polynomial-time Turing equivalent to its decision version which does not hold for any known $NP$-complete problem. The counting version of natural $NP$-complete problems seems to have much higher complexity since they are $\#P$-complete. Finally, the lowness result [3] of GI with respect to $PP$ ($PP^{GI}=PP$) is not known to hold for any $NP$-complete problem. The lowness result of GI has been improved to $SPP^{GI}=SPP$ after Arvind and Kurur proved that GI is in $SPP$ [4].

Edit: It is known that SAT is truth-table equivalent to USAT (set of Boolean formulas with exactly one satisfying assignment) while it is not known whether GI and UGI are equivalent under polynomial time truth-table reductions.

What other (recent) results can provide further evidence that GI can not be $NP$-complete?

[1]: Uwe Schöning, "Graph isomorphism is in the low hierarchy", Proceedings of the 4th Annual Symposium on Theoretical Aspects of Computer Science, 1987, 114–124

[2]: R. Mathon, "A note on the graph isomorphism counting problem", Information Processing Letters, 8 (1979) pp. 131–132

[3]: Köbler, Johannes; Schöning, Uwe; Torán, Jacobo (1992), "Graph isomorphism is low for PP", Computational Complexity 2 (4): 301–330

[4]: V. Arvind and P. Kurur. Graph isomorphism is in SPP, ECCC TR02-037, 2002.

  • 2
    $\begingroup$ The Hidden Subgroup Problem contains as a special case GI, but I don't believe it contains any problems known to be NP-complete: see, en.wikipedia.org/wiki/Hidden_subgroup_problem. Put another way, it is plausible that a quantum computer could efficiently solve GI, but few people think a quantum computer can efficiently solve an NP-complete problem. $\endgroup$ – Sam Hopkins Jan 3 '15 at 1:51
  • $\begingroup$ Integer factorization has also resisted classification. Is graph isomorphism a "longer standing" problem than factorization? $\endgroup$ – Gerry Myerson Jan 3 '15 at 3:28
  • 1
    $\begingroup$ @GerryMyerson I think stating that GI is "longest standing" is not accurate. I have edited the post accordingly. $\endgroup$ – Mohammad Al-Turkistany Jan 3 '15 at 3:58
  • $\begingroup$ reposted (with proper reference to this question) at cstheory.stackexchange.com/questions/29266/… $\endgroup$ – Thomas Klimpel Aug 13 '15 at 8:13

A search done for a related question also turned up (as indicated in a comment) rjlipton.wordpress.com/2015/03/05/news-on-intermediate-problems:

Now Eric and Bireswar complete the triad of relations to the other intermediate problems:

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.

Here $\mathsf{RP}$ stands for randomized polynomial time, MCSP is the Minimum Circuit Size Problem, and $\mathsf{SZK}$ stands for Statistical Zero Knowledge. So we learn that if MCSP is not NP-complete and RP!=NP, then graph isomorphism is not NP-complete either.


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.