tag:blogger.com,1999:blog-3722233.post8803689043688761239..comments2023-10-04T04:25:54.403-05:00Comments on Computational Complexity: Are you smarter than a 5th grade amoeba?Lance Fortnowhttp://www.blogger.com/profile/06752030912874378610noreply@blogger.comBlogger4125tag:blogger.com,1999:blog-3722233.post-33480075870864830832019-07-03T07:06:48.426-05:002019-07-03T07:06:48.426-05:00Also the whole amoeba computation thing is ridicul...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.<br /><br />It'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.<br /><br />TruePathhttps://www.blogger.com/profile/00124043164362758796noreply@blogger.comtag:blogger.com,1999:blog-3722233.post-34284472778139624572019-07-03T06:44:39.495-05:002019-07-03T06:44:39.495-05:00While not even sorta practical there are also the ...While 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. <br /><br />Not 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.<br /><br />---<br /><br />as far as both DNA and amoeba computation go I think they should both just be regarded as parallel computation. TruePathhttps://www.blogger.com/profile/00124043164362758796noreply@blogger.comtag:blogger.com,1999:blog-3722233.post-40074086802767894352019-06-28T17:56:44.371-05:002019-06-28T17:56:44.371-05:00Cheap grad students doing research and paid cheap ...Cheap grad students doing research and paid cheap in academia and industry and sent back to India and China counts?Anonymousnoreply@blogger.comtag:blogger.com,1999:blog-3722233.post-27633748993285620192019-06-24T02:07:58.679-05:002019-06-24T02:07:58.679-05:00"Is Quantum Crypto (I know, not the same thin..."Is Quantum Crypto (I know, not the same thing) actually used?"<br /><br />https://www.insidescience.org/news/china-leader-quantum-communicationsAnonymousnoreply@blogger.com