[ExI] A breakthrough in computer science?

[Adrian Tymes]

On Nov 11, 2015 9:47 AM, "John Clark" <johnkclark at gmail.com> wrote:
> 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
​

The article doesn't detail what the improvement actually is.  Guess we're
waiting on the presentation and subsequent peer review.
-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://lists.extropy.org/pipermail/extropy-chat/attachments/20151111/c470ee95/attachment.html>