<div dir="ltr"><font size="4">László Babai says he's found a<div class="gmail_default" style="font-family:arial,helvetica,sans-serif;display:inline">​​</div> algorithm that can solve the Graph<div class="gmail_default" style="font-family:arial,helvetica,sans-serif;display:inline">​ ​</div>Isomorphism<div class="gmail_default" style="font-family:arial,helvetica,sans-serif;display:inline">​ ​</div>Problem<div class="gmail_default" style="font-family:arial,helvetica,sans-serif;display:inline">​ ​</div>in<div class="gmail_default" style="font-family:arial,helvetica,sans-serif;display:inline">​ ​</div>Quasi-polynomial<div class="gmail_default" style="font-family:arial,helvetica,sans-serif;display:inline">​ ​</div>Time, that is to say the difficulty in solving <div class="gmail_default" style="font-family:arial,helvetica,sans-serif;display:inline">​the problem​</div> <div class="gmail_default" style="font-family:arial,helvetica,sans-serif;display:inline">​would ​</div>grow with the size <div class="gmail_default" style="font-family:arial,helvetica,sans-serif;display:inline">​of​</div> the input much less than 2^n and just slightly more than n^2<div class="gmail_default" style="font-family:arial,helvetica,sans-serif;display:inline">​; that would be a huge improvement​</div>. The Graph<div class="gmail_default" style="font-family:arial,helvetica,sans-serif;display:inline">​ ​</div>Isomorphism<div class="gmail_default" style="font-family:arial,helvetica,sans-serif;display:inline">​ ​</div>Problem<div class="gmail_default" style="font-family:arial,helvetica,sans-serif;display:inline">​ ​</div>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 <div class="gmail_default" style="font-family:arial,helvetica,sans-serif;display:inline">​just ​</div>a regular computer. If Babai<div class="gmail_default" style="font-family:arial,helvetica,sans-serif;display:inline">​ ​</div>'s claim holds up it would be the most important development in <div class="gmail_default" style="font-family:arial,helvetica,sans-serif;display:inline">​</div>theoretical computer science in the last 10 years.</font><div><br><div><span style="font-family:arial,helvetica,sans-serif"><div class="gmail_default" style="font-family:arial,helvetica,sans-serif;display:inline"><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>​</div></span><div><div class="gmail_default"></div></div></div><div><span style="font-family:arial,helvetica,sans-serif"><div class="gmail_default" style="font-family:arial,helvetica,sans-serif;display:inline"><br></div></span></div><div><span style="font-family:arial,helvetica,sans-serif"><div class="gmail_default" style="font-family:arial,helvetica,sans-serif;display:inline"> <font size="4">John K Clark  </font></div></span></div></div></div>