tag:blogger.com,1999:blog-3722233.post116379401236467667..comments2023-12-07T03:00:23.146-06:00Comments on Computational Complexity: The Future of ScienceLance Fortnowhttp://www.blogger.com/profile/06752030912874378610noreply@blogger.comBlogger8125tag:blogger.com,1999:blog-3722233.post-1163878858576671752006-11-18T13:40:00.000-06:002006-11-18T13:40:00.000-06:00This is anonymous #6:I meant to write "Trevisan's ...This is anonymous #6:I meant to write "Trevisan's blog".Anonymousnoreply@blogger.comtag:blogger.com,1999:blog-3722233.post-1163878729588248282006-11-18T13:38:00.000-06:002006-11-18T13:38:00.000-06:00This comment has been removed by a blog administrator.Natachahttps://www.blogger.com/profile/07736158012257975866noreply@blogger.comtag:blogger.com,1999:blog-3722233.post-1163878613422587732006-11-18T13:36:00.000-06:002006-11-18T13:36:00.000-06:00Most of these forecasts are disappointingly predic...Most of these forecasts are disappointingly predictable: each scientist interviewed basically explains that in the next 50 years,<BR/>the whole world will be doing what they have been doing in the last 50 years.<BR/>One exception is Gowers on P=NP<BR/>(but if you read Luca Trevisan's paper, or god forbid Gowers's papers, you my have noticed that his work has actually some connections to TCS).Anonymousnoreply@blogger.comtag:blogger.com,1999:blog-3722233.post-1163850873148405792006-11-18T05:54:00.000-06:002006-11-18T05:54:00.000-06:00If such a survey would have been done in the year ...If such a survey would have been done in the year 1900 pretty much everyone in every field would have been completely wrongg.Anonymousnoreply@blogger.comtag:blogger.com,1999:blog-3722233.post-1163827879937928082006-11-17T23:31:00.000-06:002006-11-17T23:31:00.000-06:00Well, it follows straightforwardly from Goedel's r...Well, it follows straightforwardly from Goedel's reasoning that "P=/= NP" is a consequence of the thesis:<BR/><BR/>An arithmetical relation F(x1, ..., xn) is Turing-computable as 'true' for every n-ary sequence of natural numbers if, and only if, [F(x1, ..., xn)] is a PA-provable formula.<BR/><BR/>The thesis seems to be intuitively unobjectionable, even though Turing's reasoning indicates that it is neither 'provable' nor 'disprovable' effectively, since we cannot establish, for an arbitrary "F(x1, ..., xn)", that "F(x1, ..., xn) is Turing-computable as 'true' for every n-ary sequence of natural numbers".<BR/><BR/>So, is it fair to conclude that the resolution of the P versus NP problem would, necessarily, be as profound as, and "rank alongside the famous undecidability results of Kurt GĂ¶del and Alan Turing"?<BR/><BR/>BhupAnonymousnoreply@blogger.comtag:blogger.com,1999:blog-3722233.post-1163809172537582862006-11-17T18:19:00.000-06:002006-11-17T18:19:00.000-06:00I wonder if we were to replace one of these blurbs...I wonder if we were to replace one of these blurbs with some 5th grader's dream of the future, if anyone would be able to identify which one it was.<BR/><BR/>(Not that they aren't fascinating.)Anonymousnoreply@blogger.comtag:blogger.com,1999:blog-3722233.post-1163802479745981692006-11-17T16:27:00.000-06:002006-11-17T16:27:00.000-06:00Anonymous said... Who are you referring to when yo...<I>Anonymous said... Who are you referring to when you say that some are over-rated? Wolfram? Chaitin?</I> <BR/><BR/>Chaitin's comment: "In my own field, I hope the current desiccated, formal approach has died out and people are more adventurous and creative." <BR/><BR/>That's gonna make him some friends. :)Anonymousnoreply@blogger.comtag:blogger.com,1999:blog-3722233.post-1163795206342440912006-11-17T14:26:00.000-06:002006-11-17T14:26:00.000-06:00Who are you referring to when you say that some ar...Who are you referring to when you say that some are over-rated? Wolfram? Chaitin?Anonymousnoreply@blogger.com