## Monday, August 9, 2010

### P vs. NP cont'd...

Mark Chu-Carroll over at "Good Math, Bad Math" blog takes a stab at explaining the basics of the 'P vs. NP' problem and its significance to us math also-rans:

http://scientopia.org/blogs/goodmath/2010/08/09/holy-freaking-cow-p-np/#more-952

The just-released 'proof' is already creating a tremendous buzz in the mathworld, as it gets analyzed by those who understand the abstract depths and intricacies of the problem. It's commonplace for glitches or shortcomings to be found in such complex proofs that require fixes or work-arounds, but will there be a fatal flaw??? If not, the Millennium Prize Problems will be down, in due time, to just five!

ADDENDUM: and here's another decent attempt, from M.I.T. this time, to explain P vs. NP to us layfolk:
http://web.mit.edu/newsoffice/2009/explainer-pnp.html

and a 2nd ADDENDUM!:  just an interesting quotation from Keith Devlin's opening to his chapter on the P vs. NP problem in his 2002 book, "The Millennium Problems":
"Of all the Millennium Problems, the P versus NP puzzle is the one most likely to be solved by an 'unknown amateur' --- someone largely untrained in mathematics, possibly someone very young, who is unknown to the mathematical community. All the other Millennium Problems are buried deep within a mass of heavy-duty mathematics, which has to be mastered before you can begin working on the problem itself. This is not the case for the P versus NP problem, which deals with how efficiently computers can perform certain kinds of tasks. Not only is it relatively easy to understand what the problem says, it is possible that all it will take to solve it is one good new idea. And you don't need lots of knowledge to have a good idea, just imagination."