On Wed, Nov 11, 2015 at 11:33:23PM +0100, Telmo Menezes wrote: > 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. >
Agreed with that. Graph isomorphism was widely believed to not be NP, and is certainly not NP-hard, but all algorithms to date have been NP (although efficaceous for practical sized problems), so this is certainly interesting. I'm not sure what the graph isomorphism problem has to do with quantum chemistry n-body simulation, though, which is a horridly combinatorial problem, even when doing Hartree-Foch approximations. Some of the biggest users of the supercomputers I managed were quantum chemists. Cheers -- ---------------------------------------------------------------------------- Prof Russell Standish Phone 0425 253119 (mobile) Principal, High Performance Coders Visiting Professor of Mathematics [email protected] University of New South Wales http://www.hpcoders.com.au ---------------------------------------------------------------------------- -- 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.
