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.