Communications of the ACM
Landmark Algorithm Breaks 30-Year Impasse
A new algorithm is being hailed as a breakthrough in mapping the difficulty of solving computational problems.
Credit: Jeremy Kun
Computer scientists are calling a new algorithm a breakthrough in mapping how hard computational problems are to solve.
Developed by University of Chicago theoretical computer scientist Laszlo Babai, the new algorithm for the "graph isomorphism" problem is significantly more efficient than the previous best offering, which held the record for more than 30 years.
The graph isomorphism question asks if two networks that look different are really the same. The problem is easy to state, but is tricky to solve because even small graphs can be made to look very different just by moving their nodes around.
Announced in November, the algorithm showed highly symmetrical "Johnson graphs" were the only case which its painting scheme did not cover. The new algorithm moves graph isomorphism much closer to P than ever before, according to Babai. He says it is quasi-polynomial, which means for a graph with n nodes, the algorithm's running time is comparable to n raised not to a constant power, but to a power that grows very slowly.
Babai has submitted a paper on his work to ACM's 48th Symposium on Theory of Computing (STOC 2016), which takes June 18-21, 2016, in Cambridge, MA.
From Quanta Magazine
View Full Article
Abstracts Copyright © 2015 Information Inc., Bethesda, Maryland, USA
No entries found