3 ms·

Have you looked for intuitive arguments about why P ≠ NP? Scott Aaronson's blog is a good place to find such things [1]: > If P=NP, then the world would be a p

Have you looked for intuitive arguments about why P ≠ NP? Scott Aaronson's blog is a good place to find such things [1]: > 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. Complexity theorists have also found more formal reasons why it it would be hard to prove P ≠ NP. For example, you can't use "natural" proofs, "relativizing" proofs, or "algebrizing" proofs [2]. (Conversely, in a P=NP world you'd expect it to be easy to prove P=NP.) 1: http://www.scottaaronson.com/blog/?p=122 http://www.scottaaronson.com/blog/?p=122 2: http://www.math.ias.edu/~avi/PUBLICATIONS/MYPAPERS/SCOTT/alg.pdf http://www.math.ias.edu/~avi/PUBLICATIONS/MYPAPERS/SCOTT/alg...

danbruc 11y ago
When I mentioned writing a symphony I was essentially referring to your quote from Scott Aaronson and I am also aware that some known proofing methods have been shown not to be strong enough to settle the question. I don't really buy into most of the examples of the quote. For example it is already a complex problem to quantify what makes a symphony a great symphony, once you solved this it of course becomes easy to recognize great symphonies. To write a great symphony you could then just exhaustively search the space of symphonies and rate them until you find a great one. But does it really sound highly implausible to you that once you figured out what makes a symphony a great symphony you could use that knowledge to prune the search space and discover great symphonies much faster that using exhaustive search? And the fact that known techniques are not good enough to settle the question doesn't sound like a surprise to me either. The very fact that the problem is not yet settled means that the usual approaches don't work and we have to use known things in an innovative way or come up with something entirely new. So that some things don't work hardly comes as a surprise but not even this implies that P == NP is more likely right or more likely wrong, it just says that figuring it out is hard. You could maybe argue that it is evidence for the problem being independent from ZFC or whatnot if we and our tools constantly fail to settle the problem one way or the other.

danbruc 11y ago

When I mentioned writing a symphony I was essentially referring to your quote from Scott Aaronson and I am also aware that some known proofing methods have been shown not to be strong enough to settle the question. I don't really buy into most of the examples of the quote. For example it is already a complex problem to quantify what makes a symphony a great symphony, once you solved this it of course becomes easy to recognize great symphonies. To write a great symphony you could then just exhaustively search the space of symphonies and rate them until you find a great one. But does it really sound highly implausible to you that once you figured out what makes a symphony a great symphony you could use that knowledge to prune the search space and discover great symphonies much faster that using exhaustive search? And the fact that known techniques are not good enough to settle the question doesn't sound like a surprise to me either. The very fact that the problem is not yet settled means that the usual approaches don't work and we have to use known things in an innovative way or come up with something entirely new. So that some things don't work hardly comes as a surprise but not even this implies that P == NP is more likely right or more likely wrong, it just says that figuring it out is hard. You could maybe argue that it is evidence for the problem being independent from ZFC or whatnot if we and our tools constantly fail to settle the problem one way or the other.