The fraternity of problems that confound computers has lost a prominent member. Computer scientist László Babai presented a new algorithm this year that efficiently tackles the graph isomorphism problem. It’s a type of problem that computers struggle to solve, even though a solution provided in advance is easily verified. Assuming it is confirmed, says Stanford theoretical computer scientist Ryan Williams, this is the biggest advance in the field in more than a decade.
The problem requires computers to compare two graphs, or networks of connected points, and determine whether all points are linked in the same way. Previously, the time required to solve the problem rose nearly exponentially with graph size. Babai’s algorithm, born from decades of mathematical effort, keeps the required computing time under control by solving even the hardest cases in what’s called quasipolynomial time (SN: 12/12/15, p. 6). Babai’s proof may provide insights for factoring large numbers and cracking other problems with easytocheck, hardtosolve status.
