Complexity Theory: Breakthrough

                                               These two networks are identical!

 

Adrian Cho of Science magazine has an interesting article about these different diagrams that are, in fact, identical with respect to which items are connected with which other items.  Laslo Babai, a computer scientist and mathematician from the University of Chicago, has come up with a computer program that determines whether or not two different-looking networks like those above really are the same.

This is a  very important advance in “complexity theory,”  which is the study of what is easy – or hard – to solve on a computer.

Babai is presenting his work this month and other scientists will be checking on it for accuracy.

 

A full story on this is available at this link:

http://news.sciencemag.org/math/2015/11/mathematician-claims-breakthrough-complexity-theory