# Computer scientist claims to have solved the graph isomorphism problem

##### November 12, 2015 by Bob Yirka weblog

(Phys.org)—László Babai with the Department of Computer Science and Mathematics at the University of Chicago has caused a lot of excitement in the computer science community by announcing recently during a lecture that he had developed an algorithm that solves the graph isomorphism problem. Though not as well known, it is comparable to someone solving the famous traveling salesmen problem.

The new algorithm, if it passes muster with other researchers, is not likely to cause any changes that non- people will notice, but solving it is an impressive achievement. Many in the field have thought doing so was impossible.

Computer science at its root is very simple—get a computer to perform a calculation we want done. Developing an algorithm that sorted records in a database, for example, was a big deal many years ago because it meant humans no longer had to do it by hand. Unfortunately, it has proven to be exceptionally difficult to get a computer to perform some other calculations, like asking it to tell a salesmen which is the best route for him, given a certain number of parameters. For a computer to do it, means grinding through all the options, which is fine for simple routes with few nodes—add hundreds, thousands or millions though, and the computer will be at it longer than the person waiting for it will live. It would be better if someone could figure out a way to tell the computer how to do it in a smarter, more efficient way—and that is what lies at the heart of computer science.

Over time, computer scientists have come up with a way to separate the easy or simple types of algorithm objectives, from those that are hard, or even thought to be impossible. Those that are relatively easy are denoted by P, because they can be run in polynomial time. Those that are hard are deemed Nondeterministic Polynomial, or just NP. The hardest of all are referred to as NP complete.

The graph isomorphism problem has been labeled as NP, though some have suggested it should be NP complete—it involves trying to create an algorithm able to look at two networks (with nodes and links between them) and report back if they are the same. Again, this is pretty simple if the network is small, but adding more complexity makes it increasing difficult to churn through. To solve this problem would require developing an algorithm that finds an answer in smart way, rather than just having a computer grind through all the options—and that is the type of algorithm that Babai believes he has created. Unfortunately, an has not yet been created to test such algorithms, thus, it will have to be vetted by other experts in the field before it can be labeled as a success.

## Related Stories

#### Simon's algorithm run on quantum computer for the first time—faster than on standard computer

November 17, 2014

(Phys.org) —A team of researchers working in South Africa has reported that they've successfully run Simon's algorithm on a quantum computer for the first time. In their paper published in Physical Review Letters, the team ...

#### Researchers present new breakthroughs for fundamental problems in computer science

October 19, 2015

Academics from the University of Bristol will present new breakthroughs on two fundamental problems in Computer Science. These results will be presented at the world's leading international conference in computer science ...

#### Difficulty makes Candy Crush so addictive

March 13, 2014

It's been said that in a city, you're never more than two metres away from a rat. But it seems more likely that you're never more than two metres from someone playing the puzzle game Candy Crush Saga.

#### P vs. NP -- The most notorious problem in theoretical computer science remains open

October 29, 2009

In the 1995 Halloween episode of The Simpsons, Homer Simpson finds a portal to the mysterious Third Dimension behind a bookcase, and desperate to escape his in-laws, he plunges through. He finds himself wandering across a ...

#### 40-year-old algorithm proven the best possible

June 11, 2015

Comparing the genomes of different species—or different members of the same species—is the basis of a great deal of modern biology. DNA sequences that are conserved across species are likely to be functionally important, ...

#### Help solve Santa's logistics troubles with a little maths

December 23, 2013

In just one night, Santa has to visit millions of homes to deliver presents. If he could travel at the speed of light, the task would be simple.

## Recommended for you

#### Digitally reconstructed skull and face may reveal Robert the Bruce, king-hero of the Scots

December 9, 2016

Could this be the face of Robert the Bruce, as it has never been seen before?

#### Mobile money access lifted two percent of Kenyan households out of poverty: study

December 8, 2016

Since 2008, MIT economist Tavneet Suri has studied the financial and social impacts of Kenyan mobile-money services, which allow users to store and exchange monetary values via mobile phone. Her work has shown that these ...

#### Amber specimen offers rare glimpse of feathered dinosaur tail

December 8, 2016

Researchers have discovered a dinosaur tail complete with its feathers trapped in a piece of amber. The finding reported in Current Biology on December 8 helps to fill in details of the dinosaurs' feather structure and evolution, ...

#### Report proposes standards for sharing data and code used in computational studies

December 8, 2016

Reporting new research results involves detailed descriptions of methods and materials used in an experiment. But when a study uses computers to analyze data, create models or simulate things that can't be tested in a lab, ...

#### Fossilized evidence of a tumor in a 255-million-year-old mammal forerunner

December 8, 2016

When paleontologists at the University of Washington cut into the fossilized jaw of a distant mammal relative, they got more than they bargained for—more teeth, to be specific.

#### Scheduling leisure activities makes them less fun: study

December 8, 2016

Nothing ruins a potentially fun event like putting it on your calendar. In a series of studies, researchers found that scheduling a leisure activity like seeing a movie or taking a coffee break led people to anticipate less ...

##### Doug_Huffman
5 / 5 (2) Nov 12, 2015
I see implications for QFT. Professor Susskind has ended the last few of his public lectures with the consequences of computational complexity on QFT and entanglement.
##### thefurlong
5 / 5 (4) Nov 12, 2015
No, easy problems are both in P and NP. Nondeterministic Polynomial problems are those whose answers can be confirmed in polynmial time. Another way of looking at this is that you could guess an answer (hence the non-deterministic part), and then find a deterministic algorithm to confirm the answer in polynomial time. All problems in P can be confirmed in polynomial time, hence they are in NP.

The hard problems actually belong to NP-hard. These are problems that every problem in NP can be reduced to in polynomial time. Conceptually, every problem in NP is at least as hard as every problem in NP-hard.

A very special class of NP-hard problems is NP complete problems. These also have the property that every instance of a problem can be converted to some problem in NP in polynomial time, which means that if you know an efficient algorithm for solving an NP-complete problem, you have an efficient algorithm for solving every NP problem.
##### antialias_physorg
5 / 5 (6) Nov 12, 2015
In case anyone is wondering 'what is this good for'...here's a bit of a list (see first answer post)
http://math.stack...c-graphs

This - if it turns out to be true - is potentially huge, as you can use this to see e.g. if a complex theory maps onto a simpler one (i.e. whether two theories are equivalent or not). A more concrete application would be to see whether a complex encryption scheme is vulnerable to a simple 'shortcut'.
Since machine learning is a big thing now: it could be used to find simpler neural network topologies from trained systems...potentially speeding up processing by quite a lot.
##### Doug_Huffman
not rated yet Nov 12, 2015
Oops
5 / 5 (2) Nov 12, 2015
As often, Yirka's article gets me an headache when I attempt to make a reasonable translation into what was actually claimed.

Babai's result, which was in rumor before the press release, is an improvement in speed on existing bounds.

Yes, you can always claim the problem is "impossible" if you increase its size. But as the illustration shows, it is solvable and indeed solved for a great many cases.

[tbctd]
5 / 5 (2) Nov 12, 2015
[ctd]

"Earlier today, I was tipped off to what might be the theoretical computer science result of the decade. ...

... the legendary Laszlo Babai will be giving a talk about a new algorithm that solves the graph isomorphism problem in quasipolynomial time. The previous fastest algorithm to decide whether two n-vertex graphs G and H are isomorphic—by Babai and Luks, back in 1983—ran in exp(√(n log n)) time. If we credit the announcement, Babai has now gotten that down to exp(polylog(n)), putting one of the central problems of computer science "just barely above P." (For years, I've answered questions on this blog about the status of graph isomorphism—would I bet that it's in BQP? in coNP? etc.—by saying that, as far as I and many others are concerned, it might as well just be in P. Of course I'm happy to reaffirm that conjecture tonight.)"

[ http://www.scotta.../?p=2521 ]

[tbctd]

5 / 5 (2) Nov 12, 2015
[ctd]

"Babai: this is a purely theoretical enterprise. Brandon McCay have a very fast algorithm. This will not challenge theirs ...

Babai just gave the sketch proof of the algorithm-- which will probably not be faster than any of the existing algorithms in practice ...

After the talk, I spoke w Babai. Why is this result impractical? Because existing algorithms are already very fast in practical cases. ...

One of the challenges is that there aren't even any known examples where the existing heuristics perform slowly. ...

[ https://storify.c...ism-talk ]
##### ogg_ogg
5 / 5 (1) Nov 12, 2015
@thefurlong
Did you really mean to write:"Conceptually, every problem in NP is at least as hard as every problem in NP-hard." ???
Just say it ain't so, Joe.
##### ogg_ogg
4 / 5 (1) Nov 12, 2015
I find the entire field uninteresting because it assumes the existence of what I call a "floor" for NP-Hardness (ie. the minimum maximum). I'd suggest there is no upper bound on difficulty. Understanding women is an example :p
##### thefurlong
5 / 5 (1) Nov 12, 2015
@thefurlong
Did you really mean to write:"Conceptually, every problem in NP is at least as hard as every problem in NP-hard." ???
Just say it ain't so, Joe.

Haha. Thanks for catching my typo. I meant that every problem in NP is AT MOST as hard as every problem in NP-hard.