On Wed, Nov 11, 2015 at 6:50 PM, John Clark <[email protected]> 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. > This is an exciting result indeed, but I'm not sure it is so relevant for simulated chemistry. Aren't there NP-hard problems involved that have nothing to do with graph isomorphism? Also, I think the molecular graph isomorphism was already solvable in quadratic time because it's a simpler problem: no self-loops, the vertices are labeled by a finite set (the elements) and each label introduces further restriction on the degree of a vertex. Maybe I'm missing something? Telmo. > 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. > -- 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.
