"That would be the most interesting possibility, Trevisan said, since it would make graph isomorphism the first natural problem to have a quasi-polynomial algorithm but no polynomial algorithm. "
"Proving it would amount to solving the P versus NP problem, since it would mean that graph isomorphism separates the problems in P from the NP-complete problems."
(exp((log n)^O(1)))
Interesting that there could be a much more varied landscape than was previously thought.
"Proving it would amount to solving the P versus NP problem, since it would mean that graph isomorphism separates the problems in P from the NP-complete problems."
(exp((log n)^O(1)))
Interesting that there could be a much more varied landscape than was previously thought.