(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
(e.g.,
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!
"Is Quantum Crypto (I know, not the same thing) actually used?"
ReplyDeletehttps://www.insidescience.org/news/china-leader-quantum-communications
Cheap grad students doing research and paid cheap in academia and industry and sent back to India and China counts?
ReplyDeleteWhile not even sorta practical there are also the papers about relativity computation, e.g., can you compute the halting problem by throwing your computer into a blackhole or sending it on some other trajectory through curved space and communicating with it along the way.
ReplyDeleteNot practical but does raise some interesting questions about the physics, e.g., are we guaranteed that being able to communicate back to your starting point after any finite time has passed for you requires infinite initial energy for any path that allows a message you sent after arbitrarily large finite time reach your starting point all within some bounded time. Or is there some way you can take advantage of your trajectory to always accumulate sufficient energy that you can shoot a message back if you see your TM halt.
---
as far as both DNA and amoeba computation go I think they should both just be regarded as parallel computation.
Also the whole amoeba computation thing is ridiculous and their paper should have probably been sent back and publication refused until they removed the computational complexity claims. I mean this seems obviously just another instance of those claims about soap bubble computation that Scott Aaronson has nicely empirically countered.
ReplyDeleteIt's obviously applying a kind of semi-greedy/local optimization algorithm which we know isn't interesting from a computational point of view here. And linear time doesn't seem at all surprising given all they are doing is finding the local minimum and the local computations are happening in parallel.