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.
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.
Subscribe to:
Post Comments (Atom)
Who are you referring to when you say that some are over-rated? Wolfram? Chaitin?
ReplyDeleteAnonymous said... Who are you referring to when you say that some are over-rated? Wolfram? Chaitin?
ReplyDeleteChaitin'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:
ReplyDeleteAn 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"?
Bhup
If such a survey would have been done in the year 1900 pretty much everyone in every field would have been completely wrongg.
ReplyDeleteMost of these forecasts are disappointingly predictable: each scientist interviewed basically explains that in the next 50 years,
ReplyDeletethe 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.
ReplyDeleteThis is anonymous #6:I meant to write "Trevisan's blog".
ReplyDelete