10
$\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.

$\endgroup$
  • 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 '15 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 '15 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 '15 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 '15 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 '15 at 16:10
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.

$\endgroup$

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.