Theoretical computer scientists are normally a fairly sedate bunch, but are humming with excitement after a potential breakthrough in a long-standing problem called graph isomorphism.
The result could provide a deeper understanding of the nature of computing and “might be the theoretical computer science result of the decade”, according toof the Massachusetts Institute of Technology.
Graph isomorphism concerns whether two graphs – the mathematical term for a network of links and nodes – are the same, even if they look different. The problem crops up in a number of applications, such as determining the identity of complex molecules. But because only the connections between nodes matter, and not their spatial placement, it can be hard to decipher the tangle and match one graph to another.
Nowof the University of Chicago, Illinois, speaking in a lecture yesterday, has announced that this may be easier than previously thought.
Looking at such questions is the bread and butter of complexity theorists, who seek to classify computational problems by how difficult they are to solve. Take multiplying together two numbers that each have n digits, a calculation that requires about n² computational steps. Complexity theorists call the level of difficulty involved in this calculation polynomial time, and place basic multiplication in the class P. In broad terms, problems in this class are easy for computers to solve.
The biggest open question in complexity theory asks how these P problems relate to those in another class, NP. If you are given a solution to an NP problem, it’s easy to check whether it is correct, but for some of the hardest problems in this class – known as NP-complete – finding a solution in the first place can be very difficult. An example is the travelling-salesman problem, which asks whether it is possible to find a route shorter than a given length around a group of cities.
The mystery is whether these two problem classes, P and NP,. It’s thought that they aren’t, because P problems are “easy” and NP-complete ones are “hard”, but no one has been able to prove this despite decades of research – and the answer is .
So how does graph isomorphism fit in? When the P versus NP issue first reared its head in the 1970s, theorists set about sorting problems into P or NP-complete, but graph isomorphism stubbornly refused to be boxed in. They knew it was in NP – given a match between two graphs, you can easily check its correctness – but was it NP-complete?
Babai’s new result says that solving graph isomorphism takes slightly longer than polynomial time – not quite placing it in P, but significantly shifting the needle for the first time.
People have spent so much time studying the problem with little progress that theorists call it the, says of Stanford University. A breakthrough is therefore a big deal – not quite the equivalent of particle physicists discovering the Higgs boson, but close. “I’d put it on the level of discovering some new property of a particle that many, many people have studied,” he says.
The result is unlikely to help with software used to tackle graph isomorphism problems because existing solvers work fine for graphs relating to practical problems. It also doesn’t directly address the P versus NP question, but it could provide new ways of attacking it.
“It shows a power of algorithms we didn’t know before,” says Williams. “In that sense, it’s addressing the same kinds of issues we address when we talk about things like P versus NP.”
Babai declined to be interviewed about the work, saying it must first stand up to the scrutiny of peer review. “I understand that in the internet age, even a simple seminar announcement can trigger an explosion in the blogosphere, but this is no reason to compromise the process,” he says. “The reaction of colleagues at this point is not celebration but anticipation. The results need to be verified by the research community.”
Reports from his lecture yesterday suggest that Babai’s method involves dividing a graph into different parts and solving them separately. Some of these sub-graphs, known as Johnson graphs, are particularly difficult to analyse.
To tackle those, he borrows concepts from important work in another area of mathematics called group theory, known as the classification of finite simple groups. The proof of this is famous in its own right for. “It sounds like Babai has built a monster of an algorithm,” says Williams.
This entry passed through the Full-Text RSS service – if this is your content and you’re reading it on someone else’s site, please read the FAQ at fivefilters.org/content-only/faq.php#publishers.