[ExI] A breakthrough in computer science?

[Dan TheBookMan]

> On Nov 11, 2558 BE, at 2:51 PM, Adrian Tymes <atymes at gmail.com> wrote:
> 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.
> 

I reckon. I did a quick search and didn't find anything peer-reviewed on this either. See:

http://people.cs.uchicago.edu/~laci/quasipoly.html

Anyhow, I expect it won't be long given the story in Science.

Regards,

Dan
  Sample my Kindle books via:
http://author.to/DanUst
-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://lists.extropy.org/pipermail/extropy-chat/attachments/20151111/d473cb17/attachment.html>