<html><head><meta http-equiv="content-type" content="text/html; charset=utf-8"></head><body dir="auto"><div>On Nov 11, 2558 BE, at 2:51 PM, Adrian Tymes <<a href="mailto:atymes@gmail.com">atymes@gmail.com</a>> wrote:<br></div><blockquote type="cite"><div><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></div></blockquote><br><div>I reckon. I did a quick search and didn't find anything peer-reviewed on this either. See:</div><div><br></div><div><div><span style="background-color: rgba(255, 255, 255, 0);"><a href="http://people.cs.uchicago.edu/~laci/quasipoly.html">http://people.cs.uchicago.edu/~laci/quasipoly.html</a></span></div><div id="AppleMailSignature"><span style="background-color: rgba(255, 255, 255, 0);"><br></span></div><div id="AppleMailSignature"><span style="background-color: rgba(255, 255, 255, 0);">Anyhow, I expect it won't be long given the story in Science.<br><br></span><div style="line-height: normal;"><span style="line-height: 20px; background-color: rgba(255, 255, 255, 0);">Regards,</span></div><div style="line-height: normal;"><span style="line-height: 20px; background-color: rgba(255, 255, 255, 0);"><br></span></div><div><div style="line-height: normal;"><span style="line-height: 20px; background-color: rgba(255, 255, 255, 0);">Dan</span></div><div style="line-height: normal;"><span style="background-color: rgba(255, 255, 255, 0);"> Sample my Kindle books via:</span></div><div style="line-height: normal;"><font color="#000000" style="background-color: rgba(255, 255, 255, 0);"><a href="http://author.to/DanUst" style="background-color: rgba(255, 255, 255, 0);">http://author.to/DanUst</a></font></div></div></div></div></body></html>