tag:blogger.com,1999:blog-3722233.post113663806077554855..comments2018-02-17T19:51:48.176-05:00Comments on Computational Complexity: A Search Without EndLance Fortnowhttps://plus.google.com/101693130490639305932noreply@blogger.comBlogger24125tag:blogger.com,1999:blog-3722233.post-1136901895122567342006-01-10T09:04:00.000-05:002006-01-10T09:04:00.000-05:00"I doubt it. Things like this will always make new...<I>"I doubt it. Things like this will always make news."</I><BR/><BR/>It used to be news when a graphics scene was rendered by a computer. Now thousands of CGI are generated every hour.<BR/><BR/>The point is that it's not at all about how important it is. It's important that everyone stop at red lights. It's important that children get taught. None of these are news worthy because they are an expected part of daily life. It's only the exceptions that make it news.<BR/><BR/>(Which, obviously, could be about an exceptional teacher, about an intersection that's rated the safest in the world, yes, yes, we are all clever and can think of obvious exceptions to points.)Macneilhttps://www.blogger.com/profile/16382866616548432101noreply@blogger.comtag:blogger.com,1999:blog-3722233.post-1136885834653148532006-01-10T04:37:00.000-05:002006-01-10T04:37:00.000-05:00The search for a new microscopic lubricant for use...The search for a new microscopic lubricant for use in the computer field led to the (accicental) discovery (in a rather embarrasing way ) of................<BR/><BR/><BR/>........Super Glue , one of the most valueable daily use products known to us simple minded non expansive carbon based , opinion biased homosapienic spiritual wannnabe`sAnonymousnoreply@blogger.comtag:blogger.com,1999:blog-3722233.post-1136879043190545462006-01-10T02:44:00.000-05:002006-01-10T02:44:00.000-05:00I really dislike how they find a Mersenne prime an...I really dislike how they find a Mersenne prime and then brag about how it takes so and so many pages to write down. These numbers have too little Kolmogorov complexity to be taken serious :)Anonymousnoreply@blogger.comtag:blogger.com,1999:blog-3722233.post-1136852687420191812006-01-09T19:24:00.000-05:002006-01-09T19:24:00.000-05:00I wonder - what's the largest known composite numb...I wonder - what's the largest known composite number? And why do they never make the news? :-)Anonymousnoreply@blogger.comtag:blogger.com,1999:blog-3722233.post-1136840484921101332006-01-09T16:01:00.000-05:002006-01-09T16:01:00.000-05:00I agree with the meta-question:"What do you mean W...I agree with the meta-question:<BR/>"What do you mean <I>Why</I>?"<BR/><BR/><I> Why did they do it? </I> <BR/><BR/>Who knows. Maybe they like holding the record for biggest prime number. People like holding records. It's nice to be the best at something. I'm enough of a geek that I think having found the biggest prime number on record would be a very cool thing. <BR/><BR/><I> Why would it be considered good research? </I> <BR/><BR/>I'm not sure anyone actually said it was. My experience suggests that when something scientific appears in the news, that does not mean it's good research, and of course lots of worthy research never makes the news! <BR/><BR/>It may be good research, or it may just be an exercise in taking old research and doing it on shinier, newer machines. I don't know enough to say. From the comments, I'm not sure anyone else really has any compelling argument one way or another. <BR/><BR/><I> Why would this be in the news? </I> <BR/><BR/>People can understand it. Most laymen know what a prime is. Finding big primes for a long time was something of a computational challenge problem, so many people (including perhaps science writers for the newspaper) can grok the story. They can imagine that finding big primes represents some sort of mathematical progress. We might suspect that it really doesn't, but so what? It apparently sells newspapers. <BR/><BR/>Hey, I've got a why question!<BR/><BR/><I> Why don't we in CS theory do a better PR job and get articles like this -- or even better ones! -- in the papers describing our work? </I>Michael Mitzenmacherhttps://www.blogger.com/profile/00458446293652845258noreply@blogger.comtag:blogger.com,1999:blog-3722233.post-1136832846373164132006-01-09T13:54:00.000-05:002006-01-09T13:54:00.000-05:00"... perhaps it'll happen so frequently and predic...<B>"... perhaps it'll happen so frequently and predictabley that it could not even by definition be considered news."</B><BR/><BR/>I doubt it. Things like this will always make news. Maybe just finding the largest known prime will cease to be newsworthy, but finding a prime that has, say, ten times as many digits as the largest previously known prime will always be. Aside from the question of whether this is good research (or even research at all), the public easily grasps the results as new milestones in technology.Anonymousnoreply@blogger.comtag:blogger.com,1999:blog-3722233.post-1136827782168359612006-01-09T12:29:00.000-05:002006-01-09T12:29:00.000-05:00Littlewood was quite concerned with the distributi...Littlewood was quite concerned with the distribution of prime numbers, and thus probably saw the ability to find larger and larger primes as a great way of generating "experimental data," much the same way as a physicist might champion the building of the next generation of particle accelerators.Anonymousnoreply@blogger.comtag:blogger.com,1999:blog-3722233.post-1136775303785061662006-01-08T21:55:00.000-05:002006-01-08T21:55:00.000-05:00I happened to be reading "A Mathematician's Miscel...I happened to be reading "A Mathematician's Miscellany" by the great English mathematician Littlewood last night, and came across a rather excited discussion by Littlewood of the (then) state-of-the-art in finding large primes. It'd be interesting to know what got Littlewood so excited.<BR/><BR/>Michael NielsenAnonymousnoreply@blogger.comtag:blogger.com,1999:blog-3722233.post-1136764686348504152006-01-08T18:58:00.000-05:002006-01-08T18:58:00.000-05:00Dilbert's internet debate rule #5: "Assume the dum...Dilbert's internet debate rule #5: "Assume the dumbest interpretation. For example, if someone says that he can run a mile in 12 minutes, assume he means it happens underwater and argue that no one can hold his breath that long."Macneilhttps://www.blogger.com/profile/16382866616548432101noreply@blogger.comtag:blogger.com,1999:blog-3722233.post-1136757516464150522006-01-08T16:58:00.000-05:002006-01-08T16:58:00.000-05:00Well clearly there is still utility in searching f...Well clearly there is still utility in searching for a sense of humor.Anonymousnoreply@blogger.comtag:blogger.com,1999:blog-3722233.post-1136756398865048132006-01-08T16:39:00.000-05:002006-01-08T16:39:00.000-05:00If Jupiter had an infinite number of moons it *wou...If Jupiter had an infinite number of moons it *would* be exciting, at first. At one point it was exciting to prove that there are an infinite number of primes. Now any undergrad math major can give you that proof.<BR/><BR/>But each new moon found, provided it didn't use any heroics to do so, would not be news! In fact... it would be news if no new moons could be found.Macneilhttps://www.blogger.com/profile/16382866616548432101noreply@blogger.comtag:blogger.com,1999:blog-3722233.post-1136753461118243532006-01-08T15:51:00.000-05:002006-01-08T15:51:00.000-05:00I think people are missing the point here: If Jup...I think people are missing the point here: If Jupiter had an infinite number of moons, that would be really exciting.Anonymousnoreply@blogger.comtag:blogger.com,1999:blog-3722233.post-1136697917388205712006-01-08T00:25:00.000-05:002006-01-08T00:25:00.000-05:00Perhaps finding the actual prime number is uninter...Perhaps finding the actual prime number is uninteresting but that doesn't necessarily make the research involved uninteresting. Maybe its an application of a powerful new distributed technique. What if the research led to an "evil" computer proof of the twin prime conjecture or some other deep insight into prime numbers in general? It's a bit harsh to criticize the researchers involved without knowing their real goals.Anonymousnoreply@blogger.comtag:blogger.com,1999:blog-3722233.post-1136688758369406202006-01-07T21:52:00.000-05:002006-01-07T21:52:00.000-05:00It wasn't meant to be a complete analogy. I am in...It wasn't meant to be a complete analogy. I am in agreement that finding larger primes is not very exciting. On the other hand, factoring larger and larger composites is interesting for a number of reasons, if only so that we know how strong our cryptography has to be, but also because reductions in the exponent of factoring algorithms often require significant mathematics. So the response "It's not interesting because we'll never run out of numbers" isn't very effective.Anonymousnoreply@blogger.comtag:blogger.com,1999:blog-3722233.post-1136686503709419142006-01-07T21:15:00.000-05:002006-01-07T21:15:00.000-05:00"No matter how many theorems we prove to be true, ..."No matter how many theorems we prove to be true, there are always more to be found, thus why do mathematics at all"<BR/><BR/>That's a bad analogy. Theorems are more or less interesting, and there is a fair degree of consensus on what's interesting and what's not. As far as prime numbers are concerned, the question precisely is: why should a prime number be interesting because it's the biggest one we can discover at the present point in time using a certain technology?<BR/><BR/>The claim could be made that these newly discovered numbers are interesting for additional reasons. Perhaps the purpose of the post is to move the debate in that direction...Anonymousnoreply@blogger.comtag:blogger.com,1999:blog-3722233.post-1136682461158034852006-01-07T20:07:00.000-05:002006-01-07T20:07:00.000-05:00Actually, I think Lance's point is an excellent on...Actually, I think Lance's point is an excellent one; I wondered why this even made the news. And I don't understand why people are rushing to defend this result as some sort of great research --- it's not. (And the pseudo-relativist claims that "no one has the right to judge what is valuable research and what is not" are silly --- would you say the same thing about intelligent design? Besides, we do exactly that every time we are on a program committee or funding panel...)<BR/><BR/>If you defend this research then please give a reason (he, I might be wrong...), rather than just suggesting that there might be one.Anonymousnoreply@blogger.comtag:blogger.com,1999:blog-3722233.post-1136682093101726932006-01-07T20:01:00.000-05:002006-01-07T20:01:00.000-05:00"Lance's point is that there will always be a larg..."Lance's point is that there will always be a larger prime number to be found, no matter how many we find."<BR/><BR/>I hope this is not Lance's point, because it's not a very good one.<BR/><BR/>By the same reasoning:<BR/>"No matter how many theorems we prove to be true, there are always more to be found, thus why do mathematics at all?"Anonymousnoreply@blogger.comtag:blogger.com,1999:blog-3722233.post-1136681009737226152006-01-07T19:43:00.000-05:002006-01-07T19:43:00.000-05:00Lance's point is that there will always be a large...Lance's point is that there will always be a larger prime number to be found, no matter how many we find.<BR/><BR/>I predict it will still be big news so long as the findings sound like a heroic effort (using 700 computers over many years *is* heroic). After that, it will only be special barriers or special awards that will get any attention. Finally, perhaps it'll happen so frequently and predictabley that it could not even by definition be considered news.Macneilhttps://www.blogger.com/profile/16382866616548432101noreply@blogger.comtag:blogger.com,1999:blog-3722233.post-1136676493519249842006-01-07T18:28:00.000-05:002006-01-07T18:28:00.000-05:00Progress on finding larger and larger prime number...Progress on finding larger and larger prime numbers used to involve a mix of mathematical ingenuity and engineer prowess. But these days, it basically scales with the power of emerging technology. On the other hand, I think it would be difficult to argue that the task of finding large primes _drives_ the emergence of technology. In this sense, finding larger primes is merely a symptom of better technology, and thus wouldn't be classified as research.<BR/><BR/>Advances in factoring larger and larger composites, on the other hand, often involves significant mathematical breakthroughs.<BR/><BR/>Hopefully this is a clear enough distinction to justify Lance's point.Anonymousnoreply@blogger.comtag:blogger.com,1999:blog-3722233.post-1136675903347339982006-01-07T18:18:00.000-05:002006-01-07T18:18:00.000-05:00"This attitude implies that no research is any mor..."<EM>This attitude implies that no research is any more or less valuable than any other.</EM>"<BR/><BR/>But who is to judge whether a piece of research is valuable or not? One popular (though not always correct) judge of the usefulness of research is whether it has immediate applications, or whether agencies like NSF fund you for your efforts. But that is hardly a good judge of the value of a piece of research, is it? Viewed this way, research in abstract mathematics would cease to exist. <BR/><BR/>Not that finding large primes is in any way abstract mathematics, but this debate brings about an interest ing question "<B>What is good research?</B>". I wish that Lance would start a blog entry on this to solicit more feedback from his readers on answers to this question.Anonymousnoreply@blogger.comtag:blogger.com,1999:blog-3722233.post-1136671705818943122006-01-07T17:08:00.000-05:002006-01-07T17:08:00.000-05:00"But that is a subjective question whose answer de..."But that is a subjective question whose answer depends on who [sic] you ask."<BR/><BR/>This attitude implies that no research is any more or less valuable than any other. Viewed in this light, it seems clear that either some other justification is required or all our jobs are in jeopardy.<BR/><BR/>There are several obvious, though, perhaps, not entirely satisfactory answers: It is a mathematical achievement that the lay person can easily understand (this is evidenced by the fact that clips describe the size of the prime in terms of how many pages it fills, hardly a scientific explanation). The previous commentator gives another explanation. Finally, new concepts may be conquered in the quest to find such numbers (such as distributed computing, Mersenne primes, or other things I don�t really understand or care much about).Anonymousnoreply@blogger.comtag:blogger.com,1999:blog-3722233.post-1136666022959541502006-01-07T15:33:00.000-05:002006-01-07T15:33:00.000-05:00Dr. Odlyzko wrote:". . . Finding an additional pri...Dr. Odlyzko wrote:<BR/><BR/>". . . Finding an additional prime doesn't enlighten us very much . . ."<BR/><BR/>The search itself may be uninteresting to some, but it is a hobby to others.<BR/><BR/>Much like Sudoku (known as Number Place in Dell Puzzle books for 15+ years until the recent marketing wave and popularity increase) and a sense of accomplishment upon completion of a puzzle, finding a big (and I use that term loosely) prime number probably provides that same sense. Again, like Sudoku, the search for primes is the application of known algorithms to the search space, as opposed to the discovery of new theory. Like other forms of "mental golf", I think it is healthy.Anonymousnoreply@blogger.comtag:blogger.com,1999:blog-3722233.post-1136662579608286582006-01-07T14:36:00.000-05:002006-01-07T14:36:00.000-05:00What do you mean Why?. Perhaps these guys know som...What do you mean <EM>Why?</EM>. Perhaps these guys know something about the number that you don't. To you it seems a useless quest because, I presume, "it does not seem to have any application". But that is a subjective question whose answer depends on who you ask. What seems useless to you may seem useful to a mathematician. And what seems immensely useful and important to you may be totally useless to a more empirical person.Anonymousnoreply@blogger.comtag:blogger.com,1999:blog-3722233.post-1136640613754003792006-01-07T08:30:00.000-05:002006-01-07T08:30:00.000-05:00From www.mersenne.org: "The new prime is 9,152,052...From www.mersenne.org: "The new prime is 9,152,052 digits long. This means the Electronic Frontier Foundation $100,000 award for the discovery of the first 10 million digit prime is still up for grabs!"<BR/><BR/>And from www.eff.org/awards/coop.php: "The Electronic Frontier Foundation (EFF), the first civil liberties group dedicated to protecting the health and growth of the Internet, is sponsoring cooperative computing awards, with over half a million dollars in prize money, to encourage ordinary Internet users to contribute to solving huge scientific problems."<BR/><BR/>Perhaps "ordinary Internet users" get interested in (scientific) computing.Anonymousnoreply@blogger.com