Recent Result on Graph Isomorphism

A recent result has shown that the graph isomorphism problem can be solved in quasi-polynomial time, while the general belief is that only exponential time algorithms are possible for propositional satisability. This is somewhat counter-intuitive, since for propositional satisability, we need to look for one of 2n options, while in graph isomorphism, we need to look for one of n! options, and n! ≫ 2n. Our qualitative explanation for this counter-intuitive fact comes from the fact that, in general, a graph isomorphism problem has a unique solution { in contrast to propositional satis ability which, in general, has many solutions { and it is known that problems with unique solutions are often easier to solve