11
$\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 $NP$-complete problems seems to have much higher complexity. 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].

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

I posted the question on Mathoverflow without getting an answer.

[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$
9
  • 8
    $\begingroup$ How much more evidence do you need? Let me turn the question around: What evidence is there that GI is not in P? $\endgroup$
    – Lance Fortnow
    Jan 24, 2015 at 18:23
  • $\begingroup$ @LanceFortnow I think the fact that we do not have even a quasi-polynomial time algorithm for GI is the best evidence that GI is not in $P$. Are you aware of others? $\endgroup$
    – Mohammad Al-Turkistany
    Jan 24, 2015 at 18:40
  • 2
    $\begingroup$ circumstantial evidence that GI is in P is that (afaik/afact) nobody can construct non-P hard instances (even at random?) & there dont even seem to be any (conjectured) candidates. ps this question seems close to what is the current known hardness of GI $\endgroup$
    – vzn
    Jan 24, 2015 at 19:53
  • 1
    $\begingroup$ @vzn It is HW problem to prove that if ${\sf P}={\sf NP}$, all languages in ${\sf P}$ except for $\emptyset$ and $\Sigma^*$ would be ${\sf NP}$-complete ( this is under Karp reductions). $\endgroup$
    – Mohammad Al-Turkistany
    Jan 25, 2015 at 6:10
  • 3
    $\begingroup$ @Arul See my comment to VZN. Basically, if P=NP then GI must be NP-complete under Karp reduction. $\endgroup$
    – Mohammad Al-Turkistany
    Oct 24, 2015 at 16:10

1 Answer 1

Reset to default
11
$\begingroup$

Due to Babai's recent result (see the paper) $GI$ is in quasi-polynomial time ($QP$). If $GI$ is $NP$-complete, then it implies $NP\subseteq QP=DTIME(n^{polylog\, n})$. This, in turn, implies $EXP=NEXP$, see here. Therefore, if the commonly accepted conjecture $EXP\neq NEXP$ holds, then $GI$ cannot be $NP$-complete.

Improve this answer
$\endgroup$

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.