4 ms·

Analog computers for the win.

• blamestross 6y ago
  Give me O(N) processors to solve an O(N^2) problem and I could do it in O(N) time too. The whole trope "slime mold solves TSP" is overblown.
  • karmakaze 6y ago
    TSP is NP-hard, like 2^N. The trick is that it's approximate not exact. This could be of interest compared to known heuristic algorithms.
    • blamestross 6y ago
      It is on a planar surface, with a low amount of points. Approximating it to arbitrary precision with 1 processor is polynomial. https://en.wikipedia.org/wiki/Travelling_salesman_problem#Euclidean https://en.wikipedia.org/wiki/Travelling_salesman_problem#Eu...
    • blamestross 6y ago
      > This could be of interest compared to known heuristic algorithms. The problem is that it isn't. Yes, a big enough cellular automaton can be used to solve problems, but the ratio of "processors" to "problem" isn't practical and we are not learning anything to improve heuristics because the "solution" here is only practical on a 2d surface.