1. 21
  1. 10

    A lot of nonlinear functions are approximately linear from 4 to 8… That doesn’t mean they remain linear over a useful range.

    1. 7

      I’d like to point out that fast approximate solutions to NP-hard problems are already possible with traditional algorithms.

      1. 2

        As does the article:

        conventional computers can also find approximate solutions in linear time

        1. 1

          It’s actually a bit more than that

          Of course, running some other algorithms on traditional digital computers for linear time, we can derive approximate solutions to TSP. On the other hand, when running our simulation models (AmoebaTSP or its developed versions) on the traditional computers as we did in this study, the analogue and parallel spatiotemporal dynamics require nonlinear time for simulating them as digital and serial processes. So we are trying to obtain much higher-quality solutions than those derived from the traditional ones by running our models on the analogue computers for linear time or shorter.

          It would be interesting to model the local dynamics of the amoeba with an actual computer to see if it matches up with the solution the amoeba finds. It might be insightful from an algorithmic perspective.

          In general, I think it is expected that biology solves NP-hard problems. Protein folding is another notoriously hard problem but proteins are folded in nature all the time.

      2. 5

        It’s fascinating to see how they model the traveling salesman problem to match the amoeba’s naturally occurring behaviors. Perhaps one day there will be dozens of bio-computational building blocks and an “Art of Biological Computer Programming” for reference. Of course, the ethics of harnessing living creatures for computation are complex. At the moment, I feel little empathy for the amoeba but I would be disturbed if a dolphin or chimpanzee or octopus were being used in this way.

        1. 4

          Maybe I misunderstand, but it seems like they’re using the channel illumination to penalize the amoeba for making any non-greedy choices. The heuristic appears to be a result of their modeling the environment and not the amoeba’s decision making.

          1. 2

            my question: when will the amoeba declare quantum supremacy

              1. 1

                Thank you for your comment, I’ve merged these article submissions.