<p dir="ltr">On Nov 11, 2015 9:47 AM, "John Clark" <<a href="mailto:johnkclark@gmail.com">johnkclark@gmail.com</a>> wrote:<br>
> László Babai says he's found a<br>
> ​​<br>
> algorithm that can solve the Graph<br>
> ​ ​<br>
> Isomorphism<br>
> ​ ​<br>
> Problem<br>
> ​ ​<br>
> in<br>
> ​ ​<br>
> Quasi-polynomial<br>
> ​ ​<br>
> Time, that is to say the difficulty in solving<br>
> ​the problem​<br>
>  <br>
> ​would ​<br>
> grow with the size<br>
> ​of​<br>
>  the input much less than 2^n and just slightly more than n^2<br>
> ​; that would be a huge improvement​<br>
> . The Graph<br>
> ​ ​<br>
> Isomorphism<br>
> ​ ​<br>
> Problem<br>
> ​ ​<br>
> 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<br>
> ​just ​<br>
> a regular computer. If Babai<br>
> ​ ​<br>
> 's claim holds up it would be the most important development in <br>
> ​<br>
> theoretical computer science in the last 10 years.<br>
><br>
> <a href="http://news.sciencemag.org/math/2015/11/mathematician-claims-breakthrough-complexity-theory">http://news.sciencemag.org/math/2015/11/mathematician-claims-breakthrough-complexity-theory</a>​</p>
<p dir="ltr">The article doesn't detail what the improvement actually is.  Guess we're waiting on the presentation and subsequent peer review.</p>