(title of this blog is due to Henry Baker who posted an article about this elsewhere)
Amoeba finds approx solution to TSP in linear time:here.
Over the years we have seen models of computation that claim to solve NPC or other hard problems quickly. I ask non-rhetorically and with and open mind how they have panned out.
In no particular order:
1) Parallelism. For solving problems faster YES. For speeding up how to solve NPC problems I think YES. For making P=NP somehow NO. Even so, parallel computers have been a definite practical success.
2) Quantum Computing. Will they factor large numbers anytime soon? Ever? Should we view the effort to build them as an awesome and insightful Physics experiment? Are there any problems that they are NOW doing faster? Is Quantum Crypto (I know, not the same thing) actually used? Will other things of interest come out of the study of quantum computing? It already has, see here.
3) DNA computing. Did that lead to practical solutions to NPC problems? I do not think it did. Did that lead to interesting math? Interesting biology? Interesting science? I do not know.
4) Autistic computing for finding primes: see here. Oliver Sacks, the neurologist ,claimed that two autistic twin brothers could generate large primes quickly. This story was never put to a rigorous test and may not be quite right.
5) Amoeba computing: Too early to tell. The article seems to say it succeeded on 8 cities
The problem with all of these non-standard models of computing is SCALE. And the more powerful classic computers get, the harder it is for these nonstandard models to compete.
Are these models interesting even if they don't end up getting us fast algorithms? They can be:
1) Do they lead to mathematics of interest? (Quantum- Yes, Parallelism- Yes)
2) Did they inspire algorithms for classical computers? (Quantum- Yes)
3) Do they give insight into other fields? (Quantum for Physics yes, DNA-computing for bio-??)
4) Have they ACTUALLY sped up up computations in meaningful ways for problems we care about (Parallelism has)
If you know of any result which I missed
Amoeba-computing giving insight into evolution,
Autistic computing being used by the NSA to find primes,
DNA computing leading to interesting mathematics)
then leave polite comments!