Developers Club geek daily blog

1 year, 9 months ago
The fast algorithm for a problem of graph isomorphism is published
These two graphs are isomorphic

The mathematician László Babay (László Babai) from faculty of computer sciences and mathematics of the Chicago university provided fast new algorithm for a solution of a problem of graph isomorphism — one of fundamental problems of the theory of complexity of calculations. The algorithm leads a problem very close to a class P. According to some specialists, it is one of the most considerable results in theoretical information science in a decade if not for several decades.

Declared creation of algorithm of László a month ago. According to him, the algorithm is much more effective, than the best of existing which was a champion more than thirty years: it was developed nowadays by professor Eugene Lyuks in 1983, that solved a problem for subexponential time.

László Babayu, apparently, was practically succeeded to reduce a problem to a problem of a class P: its algorithm is declared as calculated in quasi-polynomial time.

On December 11, 2015 article with the description of new algorithm at last is published in open access, and also sent to Association on ADP equipment. The official presentation of an algolritm will take place on the 48th symposium on the theory of calculations.

Within several decades the graph isomorphism problem had the special status in the theory of complexity of calculations. While hundreds of other tasks submissively gave in to classification by a class P or the class NP, could not classify a graph isomorphism problem unambiguously in any way. It seemed more difficult, than easy problems and easier, than difficult, holding unique position as though between two classes of tasks. It is one of two well-known tasks in this strange intermediate area, Scott Aaronson (Scott Aaronson), the mathematician from Massachusetts Institute of Technology says. Now, according to him "it seems that one of two gave up".

The second well-known task from "gray" area — factorization of integral numbers.

The problem of graph isomorphism in itself looks simply: it is necessary to define, two graphs are isomorphic that is whether it is possible to transform simple movement of tops one graph to another, saving communications between tops. That's all. Despite the seeming simplicity, this problem it is difficult to solve because even little graphs can take a set of the various forms.

The fast algorithm for a problem of graph isomorphism is published
László Babay represents the algorithm for a solution of a problem of graph isomorphism on November 10, 2015 at the Chicago university

László Babaya's algorithm works by virtual "coloring" of tops of the graph. At first several tops are in a random way selected, they "are colored" in different colors. Then several tops in the second graph, allegedly corresponding to tops from the first graph are selected, the same colors are appropriated to them. Eventually, all options get over. After the initial choice the algorithm colors on both graphs allegedly isomorphic tops adjoining with originally selected, in other colors until remains communications between tops.

If the algorithm of Babaya undergoes testing of colleagues, then this most considerable opening in this section of mathematics lately. "To its declaration hardly someone, except, maybe, him, assumed emergence of such result in the next ten years, if at all ever" — Joshua Grochou (Joshua Grochow) from Santa Fe institute says.

For the last several weeks Babay gave several lectures with a statement of the algorithm. Video of the first lecture of November 10 is given below.



The problem of graph isomorphism is considered "universal", that is to it it is possible to reduce any problem where the question of isomorphism of combinatory structures is raised. Usually such "universality" is inherent to problems of the class NP. At the same time the problem of graph isomorphism showed one strange property which is not present at one NP complete task: passing of "the blind test" (Arthur-Merlin's protocol).

In 2012 informal poll of scientists in the field of theoretical information science yielded such result: 14 of them expressed that the graph isomorphism problem belongs to a class P, and six told what does not belong. To László Babaya's declaration very few people thought that the problem will be solved sometime soon. "I thought that it can belongs to a class P, and can be is not present, but at my life of it nobody learns" — Grochou was recognized.

László Babay worked on a graph isomorphism problem of nearly 40 years.

This article is a translation of the original post at habrahabr.ru/post/273231/
If you have any questions regarding the material covered in the article above, please, contact the original author of the post.
If you have any complaints about this article or you want this article to be deleted, please, drop an email here: sysmagazine.com@gmail.com.

We believe that the knowledge, which is available at the most popular Russian IT blog habrahabr.ru, should be accessed by everyone, even though it is poorly translated.
Shared knowledge makes the world better.
Best wishes.

comments powered by Disqus