tag:blogger.com,1999:blog-3722233.post2839256910712073948..comments2023-12-06T02:45:43.890-06:00Comments on Computational Complexity: Finding the Right ModelLance Fortnowhttp://www.blogger.com/profile/06752030912874378610noreply@blogger.comBlogger5125tag:blogger.com,1999:blog-3722233.post-37550551920865297762010-04-07T06:27:56.930-05:002010-04-07T06:27:56.930-05:00To anonymous 2 (or anyone else who doesn't lik...<i>To anonymous 2 (or anyone else who doesn't like P as a model of efficient computation): can you suggest a better model?</i><br /><br />For sure, in fact there are some already out there. Say for example the O~(n^k) hierarchy that ignores polylog factors. Then one can define efficient computation as O~(n^2). Reductions are also more robust under this model.Anonymousnoreply@blogger.comtag:blogger.com,1999:blog-3722233.post-74727367604942453652010-04-06T21:37:57.473-05:002010-04-06T21:37:57.473-05:00To anonymous 2 (or anyone else who doesn't lik...To anonymous 2 (or anyone else who doesn't like P as a model of efficient computation): can you suggest a better model?Anonymousnoreply@blogger.comtag:blogger.com,1999:blog-3722233.post-74469270917621290082010-04-06T17:47:12.933-05:002010-04-06T17:47:12.933-05:00To previous anonymous,
We can give a similar argu...To previous anonymous,<br /><br />We can give a similar argument that real numbers do not make sense, they are not related to reality. Similarly, very big natural numbers does are not realistic. You can go on to criticize almost all of mathematics. Who care if unsolved problem like RH is false for numbers which we can not even talk about. Same for crypto. <br /><br />We idealize reality because then we can make statement about it. Every model is useful only in a restricted domain. Newton's physics is not useful for sub atomic particles but when restricted to a day to day life, people use it for building almost everything we use today, from bridges to iphone. It is the responsibility of the engineer to know the conditions he can use a result about an abstract model. <br /><br />P is useful because it gives an idealization that we can work with, and as result we find new questions. Probabilistic algorithms, ... all of these are partially result of having this abstract model. We you want use an algorithm in practice, it is your responsibility to check the specific constants about your algorithm and you machine, the range and restrictions of inputs it is going to be given, ... .<br /><br />I hope that I made the point I was trying.Anonymousnoreply@blogger.comtag:blogger.com,1999:blog-3722233.post-44659960556164607362010-04-06T09:38:49.461-05:002010-04-06T09:38:49.461-05:00Sure the class P, Polynomial-time, is not equal to...<i>Sure the class P, Polynomial-time, is not equal to efficient computation if the constants or exponents of the running time are large but it's a reasonable approximation.</i><br /><br />It isn't a reasonable approximation. If we weren't used to it and someone were to suggest it today the paper would be laughed silly and rejected outright. <br /><br />Hypothetical PC meeting:<br /><br />--hey, look at this guy, he's proposing that an O(n^100) algorithm is efficient<br /><br />--it wouldn't even work for n=2 !!<br /><br />--it also ignores constants, as if an algorithm with time complexity O(k*n^3) was worse than one with O(2^k*n^2) complexity. Hasn't this bozo read papers in parameterized algorithms showing how the former is much preferable?<br /><br />--sure, P, i.e. _polynomial_ time is closed under _polynomial_ reductions, but this is obvious, how could it be otherwise. <br /><br />--Do we even know of a problem in say Theta(n^5) that shows such class is worth studying? This is an otherwise rigged class with no natural applications.Anonymousnoreply@blogger.comtag:blogger.com,1999:blog-3722233.post-80520850624838589252010-04-06T09:03:14.195-05:002010-04-06T09:03:14.195-05:00The models I've seen have been coarse-grained ...The models I've seen have been coarse-grained and seem to simulate what people already know. I would like to see fine-grained simulations written in Erlang with lots of message passing that reveal subtleties and make us think, the way ant colonies make us ponder the mechanism of intelligent behavior. I wonder if <a href="http://www.eecs.harvard.edu/~rad/" rel="nofollow">Radhika Nagpal</a>'s work in bio-inspired multi-agent systems could be applied to economics.Geoff Knauthhttps://www.blogger.com/profile/12025560607512616605noreply@blogger.com