[ExI] A breakthrough in computer science?

[John Clark]

László Babai says he's found a
​​
algorithm that can solve the Graph
​ ​
Isomorphism
​ ​
Problem
​ ​
in
​ ​
Quasi-polynomial
​ ​
Time, that is to say the difficulty in solving
​the problem​

​would ​
grow with the size
​of​
 the input much less than 2^n and just slightly more than n^2
​; that would be a huge improvement​
. The Graph
​ ​
Isomorphism
​ ​
Problem
​ ​
involves calculating if two complicated graphs are wired up the same way or
not. If Babai's claim holds up you might not need a Quantum Computer if you
wanted to do chemical experiments by way of electronic simulation and not
in a messy lab, you might be able to do it with
​just ​
a regular computer. If Babai
​ ​
's claim holds up it would be the most important development in
​
theoretical computer science in the last 10 years.

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

 John K Clark
-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://lists.extropy.org/pipermail/extropy-chat/attachments/20151111/2e7b5d8f/attachment.html>