3 ms·
Is there any sense in which this is solving NP-complete problems in polynomial time? They're clearly aiming at NP-complete problems, but it's not clear how effi
by andrewflnr 10y ago
Is there any sense in which this is solving NP-complete problems in polynomial time? They're clearly aiming at NP-complete problems, but it's not clear how efficient this machine is or how general it is.
- nabla9 10y agoThey are developing system that could provide good heuristic solutions to NP-complete problem. That does not count as being able to _solve_ NP-complete problems. It won't find optimal solution in all cases, but it can be practically very useful. Their approach falls into the same category as simulated annealing or shrinking bubbles: https://www.technologyreview.com/s/512821/shrinking-blob-computes-traveling-salesman-solutions/ https://www.technologyreview.com/s/512821/shrinking-blob-com...