Algorithm Solves Graph Isomorphism in Record Time (2015)
&quot;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. &quot;<p>&quot;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.&quot;<p>(exp((log n)^O(1)))<p>Interesting that there could be a much more varied landscape than was previously thought.