The Complexity Theory Problem Strikes Back
From Quanta Magazine:
The legendary "graph isomorphism problem" may be harder than a 2015 result seemed to suggest.
The theoretical computer scientist László Babai has retracted
a claim that amazed the computer science community when he made it just
over a year ago. In November 2015, he announced that he had come up
with a “quasi-polynomial” algorithm for graph isomorphism,
one of the most famous problems in theoretical computer science. While
Babai’s result has not collapsed completely — computer scientists still
consider it a breakthrough — its central claim has been found, after a
year of close scrutiny, to contain a subtle error.
“In Laci Babai, you have one of the most legendary and fearsome
theoretical computer scientists there ever was, and in graph
isomorphism, one of the most legendary and fearsome problems,” wrote Scott Aaronson,
a theoretical computer scientist at the University of Texas, Austin, in
an email. “A year ago, Laci threw an unbelievable knockout punch at
[graph isomorphism], and now the problem itself seems to have gotten off
the mat and thrown a counterpunch.”
The graph isomorphism problem asks for an algorithm that can spot
whether two graphs — networks of nodes and edges — are the same graph in
disguise. For decades, this problem has occupied a special status in
computer science as one of just a few naturally occurring problems whose
difficulty level is hard to pin down.
Roughly speaking, most computer science problems fall into one of two
broad categories. There are “easy” problems, the ones that can be
solved in a polynomial number of steps — if the size of the problem is
denoted by n, the number of steps grows as, for example, n2 or n3.
These problems can (generally) be solved efficiently on a computer. And
there are “hard” problems, for which the best known algorithm takes an
exponential (such as 2n ) number of steps — far too
many for a computer to carry out efficiently. Only a handful of natural
problems, including graph isomorphism, seem to defy this dichotomy;
computer scientists have struggled for decades to figure out just where
graph isomorphism belongs.
Babai, a professor at the University of Chicago, had presented in
late 2015 what he said was a “quasi-polynomial” algorithm for graph
isomorphism. His work appeared to place the problem, if not firmly in
the easy zone, then at least in its suburbs. But on January 4 he
announced that while his algorithm still works (with some small tweaks)
and has now been carefully checked by other computer scientists, it
doesn’t run as fast as he had thought. It is “sub-exponential,” which
moves the problem back into the suburbs of the hard zone....MORE