tag:blogger.com,1999:blog-3722233.post8235385030998671321..comments2020-01-23T21:34:59.362-05:00Comments on Computational Complexity: A good article on how science is publicized gets the science wrongLance Fortnowhttp://www.blogger.com/profile/06752030912874378610noreply@blogger.comBlogger9125tag:blogger.com,1999:blog-3722233.post-22107838168814483512011-03-05T10:27:17.456-05:002011-03-05T10:27:17.456-05:00@David: Sharing the general sentiment, but then th...@David: Sharing the general sentiment, but then there is some connection between (forms of) the Riemann Hypothesis and number theoretic algorithms. <br /><br />Thus, mentioning some (vague) connection between RH and 'code-breaking' is not completely wrong.<br /><br />While saying AKS is on factoring is just wrong; leaving aside the fact that, as far as I known, while a great theoretical achievement, the 'practise' of deciding primeness was not that much influenced by it. <br /><br />Sorry, in case I got the details (or verything) wrong. I'm only a mathematician trying to prove Jeffrey Shallit right.Anonymousnoreply@blogger.comtag:blogger.com,1999:blog-3722233.post-32326739034855450302011-03-03T09:56:11.389-05:002011-03-03T09:56:11.389-05:00In popular news, it is often boiler-plate when dis...In popular news, it is often boiler-plate when discussing any topic in number theory --- even something like proofs of the Riemann Hypothesis --- to add some comments about this may have great implications for code-breaking and/or code-making. This particular example is no worse an offender than usual.Davidhttps://www.blogger.com/profile/13818371550669837787noreply@blogger.comtag:blogger.com,1999:blog-3722233.post-54134349363667141282011-03-02T22:40:03.697-05:002011-03-02T22:40:03.697-05:00Stuart Kauffman, a 'complexity theorist' o...Stuart Kauffman, a 'complexity theorist' of the Santa Fe Institute variety, wrote an (IMO) awesome, inspiring book, 'The Origins of Order', in which he nevertheless identified NP problems as 'non-polynomial'.Anonymousnoreply@blogger.comtag:blogger.com,1999:blog-3722233.post-25806927580284827902011-03-02T21:03:50.517-05:002011-03-02T21:03:50.517-05:00Jeffrey Shallit said: "And mathematicians ro...Jeffrey Shallit said: "And mathematicians routinely assert claims like "There is no formula for the prime numbers" without bothering to inquire about what this would mean."<br /><br />When I was still in the Air Force, self-teaching myself algebra with whatever scraps I could find at the base library (an ancient group theory book by Rotman), I read in that book a breathless claim that "no formula is known for the number of isomorphism classes of groups with n elements". I quickly came up with such a formula, one which was of course absolutely useless computationally and basically amounted to "programming" the function in a formula instead of in a programming language*. I thought that was a really big deal, like I'd solved some big open problem, though now I understand what I did was quite trivial.<br /><br />*(In my undergrad paper <a href="http://www.rose-hulman.edu/mathjournal/archives/2006/vol7-n2/paper2/v7n2-2pd.pdf" rel="nofollow">here</a>, I give a method for finding formulas for any computable function. The results are of course quite useless computationally!)Sam Alexanderhttp://www.xamuel.comnoreply@blogger.comtag:blogger.com,1999:blog-3722233.post-64225913151989838042011-03-02T16:46:05.235-05:002011-03-02T16:46:05.235-05:00He probably read an article about the paper, saw t...He probably read an article about the paper, saw the important bits: 3 guys from India came up with an algorithm, many people from around the world were reading it within a day, the topic is related to cryptography. Why read further to get all the facts right once he has enough information to support his thesis?Davehttps://www.blogger.com/profile/07925186895916639318noreply@blogger.comtag:blogger.com,1999:blog-3722233.post-5986177606976616352011-03-02T16:35:52.020-05:002011-03-02T16:35:52.020-05:00The real question is, why did the Royal Society ch...The real question is, why did the Royal Society choose Bill Bryson as the editor for their book?NickHhttps://www.blogger.com/profile/02726467473642434859noreply@blogger.comtag:blogger.com,1999:blog-3722233.post-71345821150811428082011-03-02T16:14:47.356-05:002011-03-02T16:14:47.356-05:00As another comment, I find the "three young I...As another comment, I find the "three young Indian mathematicians" weird. I am not saying that Manindra Agrawal was old in 2002 (nor is he right now!), but he was of course not young in the same sense as Neeraj Kayal and Nitin Saxena were. This is just to mention that my impression is that Martin Rees speaks about the AKS paper mostly by hearsay. <br /><br />Yet the question to know whether this is a big deal is left open.Anonymousnoreply@blogger.comtag:blogger.com,1999:blog-3722233.post-27292579504867435392011-03-02T15:33:04.486-05:002011-03-02T15:33:04.486-05:00Maybe it was an ironic, and very sophisticated, wa...Maybe it was an ironic, and very sophisticated, way of making the point that, on the web, a result can travel, and its correctness be checked, within days, but, via books, it takes years and, even so, mistakes are not checked.Lucahttps://www.blogger.com/profile/17835412240486594185noreply@blogger.comtag:blogger.com,1999:blog-3722233.post-18974371282154711932011-03-02T15:22:16.900-05:002011-03-02T15:22:16.900-05:00This is, unfortunately, typical.
A recent artic...This is, unfortunately, typical. <br /><br />A recent article by Freeman Dyson in the Notices of the AMS (!) confused decision problems with search problems, and P with NP. <br /><br />A 1994 book by Nobel prizewinner (in Physics) Philip Anderson claimed that NP stands for "not polynomial" and that linear programming is NP-complete. <br /><br />A book by physicist Paul Davies claimed that quantum computers could solve the traveling salesman problem efficiently. <br /><br />And mathematicians routinely assert claims like "There is no formula for the prime numbers" without bothering to inquire about what this would mean.<br /><br />I would like to propose the following maxim, which I modestly call Shallit's Law of Computational Ignorance: "Whenever a non-computer scientist makes an assertion about computational complexity, it is nearly always wrong."Jeffrey Shallithttps://www.blogger.com/profile/12763971505497961430noreply@blogger.com