Friday, 6 November 2015

A Big Result On Graph Isomorphism

A very interesting thing was mentioned in the BBC radio programme: namely that on 4 November, 2015 László Babai announced a new result for the graph isomorphism problem. You may recall that this problem is conjectured to be NP-intermediate, being neither in P or NP-complete. The new result is that there is an quasi-polynomial time algorithm for this problem. This shows that the problem is much closer to being in P than to being NP-complete. See A Big Result On Graph Isomorphism.