Your Web News in One Place

Help Webnuz

Referal links:

Sign up for GreenGeeks web hosting
November 6, 2015 08:00 pm

Breakthrough Algorithm Reported For Graph Isomorphsim

JoshuaZ writes: A major open problem in graph theory is how efficiently one can tell, given two graphs, whether or not they are isomorphic — that is, whether they're the same graph with just the labels changed. This problem is famous, along with factoring integers, as a problem that is potentially in between P and NP in difficulty. Now, Laszlo Babai has reported that he has a quasipolynomial time algorithm which he sketched out at a set of talks at the University of Chicago. Scott Aaronson was one of the first to break the news, and his latest blog entry and its comments contain further discussion of the result. The new algorithm places the problem of graph isomorphism as, at most, just barely above P. Babai's result depends on the classification of finite simple groups, a deep result in algebra whose proof consists of thousands of pages over hundreds of distinct papers. Unlike the problem of factoring integers, improvements in this algorithm are unlikely to impact cryptography in any direct way, since no cryptographic systems depend on the difficulty of determining when groups are isomorphic.

Read more of this story at Slashdot.


Original Link: http://rss.slashdot.org/~r/Slashdot/slashdot/~3/wZ9EhZ8S5nQ/breakthrough-algorithm-reported-for-graph-isomorphsim

Share this article:    Share on Facebook
View Full Article

Slashdot

Slashdot was originally created in September of 1997 by Rob "CmdrTaco" Malda. Today it is owned by Geeknet, Inc..

More About this Source Visit Slashdot