This problem gets to the heart of mathematics, because mathematical research itself has the property I have described: it seems to be easier to check that a proof is correct than to discover it in the first place. Therefore, if we found a solution to the P = NP problem it would profoundly affect our understanding of mathematics, and would rank alongside the famous undecidability results of Kurt Gödel and Alan Turing.Thanks to Chris Masse for the pointer.
Computational Complexity and other fun stuff in math and computer science from Lance Fortnow and Bill Gasarch
Friday, November 17, 2006
The Future of Science
New Scientist celebrates their 50 years by asking about 70 "Brilliant Minds" to forecast the next 50 years of science. Several researchers (all well-known though a few overrated) talk about math and computing including Tim Gowers focusing on the P versus NP problem.
Who are you referring to when you say that some are over-rated? Wolfram? Chaitin?ReplyDelete
Anonymous said... Who are you referring to when you say that some are over-rated? Wolfram? Chaitin?ReplyDelete
Chaitin's comment: "In my own field, I hope the current desiccated, formal approach has died out and people are more adventurous and creative."
That's gonna make him some friends. :)
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.ReplyDelete
(Not that they aren't fascinating.)
Well, it follows straightforwardly from Goedel's reasoning that "P=/= NP" is a consequence of the thesis:ReplyDelete
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.
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".
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"?
If such a survey would have been done in the year 1900 pretty much everyone in every field would have been completely wrongg.ReplyDelete
Most of these forecasts are disappointingly predictable: each scientist interviewed basically explains that in the next 50 years,ReplyDelete
the whole world will be doing what they have been doing in the last 50 years.
One exception is Gowers on P=NP
(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).
This comment has been removed by a blog administrator.ReplyDelete
This is anonymous #6:I meant to write "Trevisan's blog".ReplyDelete