16
$\begingroup$

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.

Improve this question
$\endgroup$
4
  • 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
    Commented Jan 3, 2015 at 1:51
  • $\begingroup$ Integer factorization has also resisted classification. Is graph isomorphism a "longer standing" problem than factorization? $\endgroup$
    – Gerry Myerson
    Commented Jan 3, 2015 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
    Commented Jan 3, 2015 at 3:58
  • $\begingroup$ reposted (with proper reference to this question) at cstheory.stackexchange.com/questions/29266/… $\endgroup$
    – Thomas Klimpel
    Commented Aug 13, 2015 at 8:13

1 Answer 1

Reset to default
4
$\begingroup$

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.

Improve this answer
$\endgroup$

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .