tag:blogger.com,1999:blog-3722233.post397116112733971482..comments2024-03-18T23:13:09.570-05:00Comments on Computational Complexity: Quotes with which I disagreeLance Fortnowhttp://www.blogger.com/profile/06752030912874378610noreply@blogger.comBlogger11125tag:blogger.com,1999:blog-3722233.post-3939225264636923292015-03-15T17:54:40.260-05:002015-03-15T17:54:40.260-05:00No..No..Anonymousnoreply@blogger.comtag:blogger.com,1999:blog-3722233.post-47524253003126342372015-03-15T07:21:51.549-05:002015-03-15T07:21:51.549-05:00Here is another quote that I really disagree with:...Here is another quote that I really disagree with: "If you can't explain it simply, you don't understand it well enough". <br /><br />This basically says that nothing is really complicated and if something is hard to understand then it's the fault of the person explaining. There is nothing that really requires thought and effort to understand.<br /><br />I couldn't disagree more!Anonymousnoreply@blogger.comtag:blogger.com,1999:blog-3722233.post-70395466842081430722015-03-14T00:54:09.094-05:002015-03-14T00:54:09.094-05:00Airports used to be even more effective working en...Airports used to be even more effective working environments: only coffee and restrooms.Daniel Marxhttp://www.cs.bme.hu/~dmarxnoreply@blogger.comtag:blogger.com,1999:blog-3722233.post-45307426933119861752015-03-12T16:02:25.272-05:002015-03-12T16:02:25.272-05:00I usually relate the Dijkstra quote paraphrased as...I usually relate the Dijkstra quote paraphrased as follows:<br /><br />Computer science is no more about computers than aerodynamics is about airplanes<br /><br />and since airplanes are one of the most important applications of aerodynamics I think this hits the right note. <br /><br />Then, I add, computer science is about what we do with information: perform computations over it, store it, transmit it, search it, display it, etc, and a standard computer is a very good way to do all of these. But we could equally discuss the efficiency of an arithmetic algorithm performed only by hand or of a sorting algorithm as implemented by a robot at a mail sorting facility, to give two examples. <br />Alex Lopez-Ortizhttps://cs.uwaterloo.ca/~alopez-o/noreply@blogger.comtag:blogger.com,1999:blog-3722233.post-67687092571537975582015-03-12T14:32:21.474-05:002015-03-12T14:32:21.474-05:00For Dijkstra, astronomical instrumentation is a hu...For Dijkstra, astronomical instrumentation is a huge sub-field of astronomy, and you can indeed get a Ph.D. for developing a better telescope.<br /><br />For Jain, the argument is that a model for which it is intractable to compute the equilibrium can't be accurate. Adding limited information and irrational actors only makes the model less accurate.<br /><br />For Stigler, taking into account the cost of missing your flight to third parties, or minimizing your own cost of being in the airport much as possible, only adjusts the optimal probability of missing your flight, but can't set it to zero, unless the total societal cost of missing your flight is infinite (it isn't), or you genuinely prefer being in the airport than at home (you don't).<br /><br />So: you disagree with Jain and Stigler because you are wrong, and with Dijkstra because you are both wrong.James Aspneshttp://www.cs.yale.edu/homes/aspnes/noreply@blogger.comtag:blogger.com,1999:blog-3722233.post-25516105101472729412015-03-12T14:18:14.537-05:002015-03-12T14:18:14.537-05:00Kamal Jain is saying that if the computational pro...Kamal Jain is saying that if the computational problem of finding an equilibrium solution is hard, then the market cannot compute the equilibrium solution either. What you are saying is that the laptop possibly cannot simulate the real world with some non-rational agents. But this is not what Kamal Jain is claiming, he is not claiming that the laptop can simulate the real world. He is just claiming that if a computational problem is hard on a compute (say in a Turing machine), then no reasonable computational model (including the market) can solve the same computational problem efficiently.Anonymousnoreply@blogger.comtag:blogger.com,1999:blog-3722233.post-56658427758891841952015-03-12T12:25:50.948-05:002015-03-12T12:25:50.948-05:00Exactly! Flights are usually too important to miss...Exactly! Flights are usually too important to miss, so the chance that you leave for it to be missed is so small, that it just practically never happens. But the situation works perfectly with buses that come every 15 minutes. I remember this whenever I miss one...domhttps://www.blogger.com/profile/05790539025733385232noreply@blogger.comtag:blogger.com,1999:blog-3722233.post-31522175566620438852015-03-12T08:54:47.803-05:002015-03-12T08:54:47.803-05:00(This is actually GASARCH)
Your tweet ``You can wr...(This is actually GASARCH)<br />Your tweet ``You can write a pithy quote and repeat it often, but that doesn't make it true'' that points to your post IS true and I will repeat it often.Anonymousnoreply@blogger.comtag:blogger.com,1999:blog-3722233.post-20006713617273305592015-03-12T08:16:28.873-05:002015-03-12T08:16:28.873-05:00The Stigler quote is no more about planes than com...The Stigler quote is no more about planes than computer science is about laptops.Boaz Barakhttps://www.blogger.com/profile/01023091208435407661noreply@blogger.comtag:blogger.com,1999:blog-3722233.post-27512070642976859752015-03-12T07:38:44.946-05:002015-03-12T07:38:44.946-05:00Minesweeper is NP-complete yet I usually win. How...Minesweeper is NP-complete yet I usually win. However, I don't *always* win. If you are willing to gamble, don't most NP-complete problems become "easy" to compute?Anonymousnoreply@blogger.comtag:blogger.com,1999:blog-3722233.post-72072600713525458282015-03-12T07:34:36.782-05:002015-03-12T07:34:36.782-05:00Ignoring gravity again, Lance?Ignoring gravity again, Lance?Anonymousnoreply@blogger.com