Hacker News new | comments | show | ask | jobs | submit login

Wikipedia on P ?= NP:

In essence, the question P = NP? asks: if 'yes'-answers to a 'yes'-or-'no'-question can be verified "quickly" can the answers themselves also be computed "quickly"?

Scott Aaronson:

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...

The problem with these grandiose statements is that they forget the word formal. You have to be searching on a space that's formally defined to make optimization=verification if P=NP. When we do art and creativity, the space is not formally defined a priori. Hell, even theorem-proving isn't. Look at the breakthroughs in mathematics and most of them, a really large majority, came from applying some new ideas or operations (e.g., ricci flows) to problems that all others simply could not see as applicable. There are no "profound philosophical implications" if P=NP (which I doubt) other than our universe lets us have polynomially bounded algorithms for a huge cluster of problems.

Guidelines | FAQ | Support | API | Security | Lists | Bookmarklet | DMCA | Apply to YC | Contact