Perhaps P is unlikely to equal NP. but not necessarily so
Could P = NP
http://en.wikipedia.org/wiki/P_versus_NP_problem
This is not an exhaustive post on the P vs. NP problem in computer science. Wiki article above is posted to give background. I am just sharing a recent thought I had, in response to a quote on the wiki article by MIT's Scott Aaronson, arguing that P cannot equal NP, intuitively. Here is the quote:
"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."
A persuasive argument, intuitively. But intuition, as any high school student of special relativity's revision of the notion of time can tell us, can mislead. I had a thought today I wanted to share, that would call the above reasoning into question.
Imagine two abstract "spaces". One space is the space of problems in P and NP, say at one end of this "space" one has P, in the middle there are some problems that could lie in either category, and towards the other end there are NP problems. Now, imagine one has another space of programs one can pick at random to solve these various problems in "problem space". So, one has "problem space" and one has "program space". With me so far? Good. Say I start randomly picking programs out of "program space" for given problems in "problem space" the only selection criteria being that the program I pick can solve the problem I am on. For any given problem, there are many possible programs I could randomly choose. Now, it will turn out, generally, that a majority of the time when I am in the "P" section of "problem space" that the programs I pick out for problems in this area will run in polynomial ("P") time. Occasionally I might pick a "bad" program to solve a polynomial-time problem (i.e. a program that will run in non-polynomial time to solve a polynomial-time problem) but this will be rare. Now, say I move along in problem space to sort of the "grey area" between P and NP problems, and now, programs I randomly pick out of my "program space" will sometimes be polynomial runtime programs, and sometimes non-polynomial (NP) runtime programs. Now, say I move further along in my problem space, so now all the problems I encounter are decidedly NP (e.g. the subset sum problem, or the famed traveling salesman problem). Now it is overwhelmingly probable that programs I pick out that can solve these problems out of my program space will themselves be NP (based on decades of research people have done on this). Probable, yes. Certain? Well that is murkier. It seems to me, that just as it is possible, if not likely, that one could pick out an NP program at random to solve a P problem, it also seems possible (if certainly very unlikely, as nobody has found one yet) to find a P program to solve an NP problem.
This is rather like entropy. In infinite space and time, Boltzmann discovered entropy generally increases, but this is a STATISTICAL thing, not an ABSOLUTE, thing, hence "Boltzmann brains", etc. It is POSSIBLE, in infinite space and time, to find someplace where entropy decreases (thus reversing the arrow of time, incidentally) but highly IMPROBABLE.
Therefore I suggest, that it could be the case that whereas it is overwhelmingly probable that in picking random programs out of a space of programs that can solve any given problem, that one will find P programs for P problems, and NP programs for NP problems, this might only be a statistical phenomena, not a necessary phenomena. Therefore, one could by accident every million or billion years of CPU time picking random programs to solve an NP problem, find a P program to solve it. If so, then, strictly speaking, P would in fact be equal to NP, but just this would not have much impact on the "real world" given its statistical improbability, similar to how one might possibly run into a Boltzmann brain, but the likelihood of this occurring is vanishingly small.
As nature herself is sort of a "program picker", using natural selection to find "programs" to solve real-world "problems" for the survival of the gene, even were P = NP strictly speaking, as outlined above, but the chances of stumbling upon a P "program" to solve an NP "problem" were very slim, then the world would in fact look much the way in fact it does look. Thus the charge that if P = NP, all who listened to Mozart would be Mozart, etc., is patently false, because here, P might strictly speaking equal NP, in terms of out there in program space there might be a polynomial-time program to solve an NP problem, but since the chances of nature (or computer scientists) stumbling upon this by accident is so slim, this would not happen much in the "real world" and thus the world would look exactly how it does look, even if P = NP. This is another example of how intuition can lead us astray by giving us something that "feels right" but does not withstand strict scrutiny.
Of course, I have no idea if P = NP or not, and if I did, I would be a wealthier individual, ha. I am just saying that fallacious intuition-based arguments do not get us any closer to resolving this conundrum one way or another, as the above "thought experiment" demonstrates. :-)