Archive for May 20th, 2009

Here’s something I plan to think about

May 20, 2009

Over on Twitter, John Pavlus started asking me about the big computer science grail, P vs NP. Sci Am’s Graham Collins boiled it down for us: “if P=NP: many seemingly v[ery] hard problems can be solved easily fr[om] scratch, we just haven’t yet found how.”  

John then pointed out this nice bit in Scott Aaronson’s blog post listing 10 reasons not to believe P=NP.

9. The Philosophical Argument. If P=NP, then the world would be a profoundly different place than we usually assume it to be. There would be no special value in “creative leaps,” no fundamental gap between solving a problem and recognizing the solution once it’s found. Everyone who could appreciate a symphony would be Mozart; everyone who could follow a step-by-step argument would be Gauss; everyone who could recognize a good investment strategy would be Warren Buffett. It’s possible to put the point in Darwinian terms: if this is the sort of universe we inhabited, why wouldn’t we already have evolved to take advantage of it? (Indeed, this is an argument not only for P!=NP, but for NP-complete problems not being efficiently solvable in the physical world.)

It’s hard to read Scott’s pedagogical material and not starting thinking about the relationship between computation and the mind. This time, by following the link at the end there, I found out there’s a cool sounding book about that very subject. Off to the library!