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 -- You received this message because you are subscribed to the Google Groups "Everything List" group. To unsubscribe from this group and stop receiving emails from it, send an email to [email protected]. To post to this group, send email to [email protected]. Visit this group at http://groups.google.com/group/everything-list. For more options, visit https://groups.google.com/d/optout.
