# Computer scientist claims to have solved the graph isomorphism problem

##### November 12, 2015 by Bob Yirka, Phys.org 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.

More information: people.cs.uchicago.edu/~laci/quasipoly.html

## 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

#### Behavioral differences between Northern v. Southern Chinese linked to wheat v. rice farming, study shows

April 26, 2018

A new study from the University of Chicago Booth School of Business analyzing behavior patterns of people across China shows that the traditional interdependent rice-farming culture of southern China has resulted in today's ...

#### How to hunt a giant sloth—according to ancient human footprints

April 26, 2018

Rearing on its hind legs, the giant ground sloth would have been a formidable prey for anyone, let alone humans without modern weapons. Tightly muscled, angry and swinging its fore legs tipped with wolverine-like claws, it ...

#### Researchers study how early humans thrived through volcanic winter

April 25, 2018

UTA researcher Naomi Cleghorn has participated in a Nature paper that describes how humans thrived in South Africa through the Toba volcanic eruption about 74,000 years ago, which created a decades-long volcanic winter.

#### Weather associated with sentiments expressed on social media

April 25, 2018

Sentiments expressed on Facebook and Twitter may be associated with certain weather patterns, according to a study published April 25, 2018 in the open-access journal PLOS ONE by Patrick Baylis from the Vancouver School of ...

#### In New Guinea, human thigh bone daggers were hot property: study

April 25, 2018

New Guinea warriors harvested thigh bones from their dead fathers to fashion into ornamental but deadly daggers used to kill and maim enemies, sometimes to eat them.

#### Archaeologists on ancient horse find in Nile River Valley

April 25, 2018

An ancient horse burial at Tombos along the Nile River Valley shows that a member of the horse family thousands of years ago was more important to the culture than previously thought, which provides a window into human-animal ...

## 10 comments

Adjust slider to filter visible comments by rank

Display comments: newest first

##### 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
##### Torbjorn_Larsson_OM
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]
##### Torbjorn_Larsson_OM
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]

##### Torbjorn_Larsson_OM
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.

Please sign in to add a comment. Registration is free, and takes less than a minute. Read more

Click here to reset your password.
Sign in to get notified via email when new comments are made.