tag:blogger.com,1999:blog-3722233.post112310222084784923..comments2023-05-28T20:30:27.485-05:00Comments on Computational Complexity: Moons and PlanetsLance Fortnowhttp://www.blogger.com/profile/06752030912874378610noreply@blogger.comBlogger9125tag:blogger.com,1999:blog-3722233.post-1123873342550175712005-08-12T14:02:00.000-05:002005-08-12T14:02:00.000-05:00I think I read somewhere that there were "proofs" ...I think I read somewhere that there were "proofs" that Gaussian elimination was optimal before Strassen discovered his algorithm.Anonymousnoreply@blogger.comtag:blogger.com,1999:blog-3722233.post-1123424967545821372005-08-07T09:29:00.000-05:002005-08-07T09:29:00.000-05:00But since some proof techniques become harder and ...<I>But since some proof techniques become harder and harder, it takes longer time to truly know what we know and what we do not know.</I><BR/><BR/>I think the advancements of computer-aided theorem-proving will solve this problem mostly. I believe that in the near future, every published math proof will have two parts: An informal part, similiar to proofs we know today, and a formal part, which is a perfectly formal deduction of the theorem. Only the most hardcore postmodern philosophers will doubt these deductions.<BR/><BR/>We need smarter automatic theorem-provers, and even more importantly, more seamless human-machine interaction to achieve this. But I think it's not that far away.Anonymousnoreply@blogger.comtag:blogger.com,1999:blog-3722233.post-1123160110217387552005-08-04T07:55:00.000-05:002005-08-04T07:55:00.000-05:00You are right.But since some proof techniques beco...You are right.But since some proof techniques become harder and harder, it takes longer time to truly know what we know and what we do not know.<BR/>For example, the four color theorem was "prooved" by Kempe in 1879. It took quite a time (11 years) to find out that a proof is incorrect (an error in the proof was discovered by Heaver). Kempe submitted his proof to the American Journal of Mathematics. Story read the paper before publication, made simplification in the proof and reported to he Scientific Association of Johns Hopkins University. <BR/>Before a mistake in the proof of Kempe was foudn, many people "KNEW" the answer to the Four-Color theorem. Kempe was ellected a Fellow of the Royal Society and was knighted.<BR/>Tait "prooved" the same theorem in 1880. Again it took 11 years to find out that Tait's proof is incorrect.Andrei Lopatenkohttps://www.blogger.com/profile/12657446705986892285noreply@blogger.comtag:blogger.com,1999:blog-3722233.post-1123138599308432122005-08-04T01:56:00.000-05:002005-08-04T01:56:00.000-05:00Let's hope the tenth "planet" has a name that begi...Let's hope the tenth "planet" has a name that begins with "t". "My very educated mother just served us nine pies TODAY". Or if another planet is discovered, name them with "l" and "w" for ". . . nine pies LAST WEEK".<BR/><BR/>In the spirit of moon.google.com, I'm still waiting for europa.google.com, io.google.com, ganymede.google.com . . .<BR/><BR/>---O<BR/><BR/>p.s. 12 (base 61) = 63 (base 10). Alternatively, 12 (base 61) = 64.512 (base 10) using Kuperberg's Principle of Expansion. 1.512 new Jupiter moons will be discovered by computer scientists.Anonymousnoreply@blogger.comtag:blogger.com,1999:blog-3722233.post-1123136065102917062005-08-04T01:14:00.000-05:002005-08-04T01:14:00.000-05:00The old mantra was that factoring is hard. The ne...The old mantra was that factoring is hard. The new mantra is that quantum computation is hard. It's TOTALLY different. :-)Anonymousnoreply@blogger.comtag:blogger.com,1999:blog-3722233.post-1123134877708917082005-08-04T00:54:00.000-05:002005-08-04T00:54:00.000-05:00Suppose for a minute that, 25 years ago, someone h...Suppose for a minute that, 25 years ago, someone had proven that factoring was hard. If you had taken a computational complexity exam, "factoring is hard" would have been a correct answer. Then along comes Peter Shor in 1994. In fact, even in mathematics the truth is time dependent. Take for example sphere eversion. There were several widely-believed "proofs" that sphere eversion was impossible until Smale came along in 1958. My only point is that people, (even mathematicians!), are fallible. Mistakes might not happen as often in computer science and mathematics as in, say, astronomy, but they still happen.<BR/><BR/>-SteveAnonymousnoreply@blogger.comtag:blogger.com,1999:blog-3722233.post-1123107292249269342005-08-03T17:14:00.000-05:002005-08-03T17:14:00.000-05:00No, even in computer science the truth is time-dep...No, even in computer science the truth is time-dependent. The prefix "kilo-" used to mean 1000; now it sometimes means 1024. Computer scientists added a 2.4% tax.Anonymousnoreply@blogger.comtag:blogger.com,1999:blog-3722233.post-1123103184389404102005-08-03T16:06:00.000-05:002005-08-03T16:06:00.000-05:00I think that's eight planets. Astronomers seem to ...I think that's eight planets. Astronomers seem to think that pluto and this new thing don't count as planets (but they do as Kuiper Belt Objects) and I'm fine with that.Anonymousnoreply@blogger.comtag:blogger.com,1999:blog-3722233.post-1123102993566066532005-08-03T16:03:00.000-05:002005-08-03T16:03:00.000-05:00Your post harks back to an earlier post of yours w...Your post harks back to an earlier post of yours which can be synthesized as: What "facts" taught in the childhood of some current students (say, in Kansas) are wrong?Anonymousnoreply@blogger.com