A Little More on the Graph Isomorphism Algorithm(rjlipton.wordpress.com) |
A Little More on the Graph Isomorphism Algorithm(rjlipton.wordpress.com) |
"[…] it could be that GI will become the first ever problem which is NP-intermediate (assuming P is not NP), but from historical patterns it seems more likely that it will fall into P. So people are excited because it’s tantalizing: everyone believes it should be in P, but nobody can prove it. It’s right at the edge of the current state of knowledge about the theoretical capabilities and limits of computation."
NP-intermediate being that space between P and NP-complete where quasipolynomial algorithms sit.
[1] http://jeremykun.com/2015/11/12/a-quasipolynomial-time-algor...