4 ms·
There's been more than a few of these "nature solves NP-hard problems quickly!" kinds of stories, but usually, when one digs deeper, the answer is "nature finds
by jcranmer 3y ago
There's been more than a few of these "nature solves NP-hard problems quickly!" kinds of stories, but usually, when one digs deeper, the answer is "nature finds local optima for NP-hard problems quickly!" and the standard response is "so does pretty trivial computer algorithms."
In the case of TSP, when you're trying to minimize a TSP with a Euclidean metric (i.e., each node has fixed coordinates, and the cost of the path is the Euclidean distance between these two points), then we can actually give you a polynomial-time algorithm to find a path within a factor ε of the optimal solution (albeit exponential in ε).
- pas 3y agohttps://scottaaronson.blog/?p=266 https://scottaaronson.blog/?p=266 """ I went to the hardware store, bought some glass plates, liquid soap, etc., and found that, while Nature does often find a minimum Steiner tree with 4 or 5 pegs, it tends to get stuck at local optima with larger numbers of pegs. """