Written: Dec. 11, 2006.
One of the highlights of the International Congress of Mathematicians (ICM2006), that took place in Madrid this past August, was undoubtedly Avi Wigderson's wonderful, insightful, lucid, inspiring, thought-provoking and uplifting plenary talk entitled "P,NP and Mathematics- a computational complexity perspective". I was not present at the original event, but I read the writeup two times and listened to a "rerun" that Avi Wigderson gave at the Rutgers Mathematics Colloquium.
It was indeed fascinating to hear about the state-of-the-art of the P vs. NP problem, addressed to the mathematical masses, by one of the great gurus of computational complexity theory, and about its possible relevance to the practice of mathematics. Also about the intuitive and heuristic reasons that the conventional wisdom (or at least the wisdom of Wigderson) gives in support of the "intuitively obvious" fact that P is not equal to NP.
But I didn't agree with everything. Some of the analogy with mathematics seemed rather far-fetched and I disagree that the content of computational complexity theory has much to offer for the practice of contemporary pure mathematics except as very vague (and often misguided) metaphors.
One thing is obvious. The theory itself is a great example of a beautiful and deep (human) mathematical theory, and as such has a lot to offer to mathematicians in other areas. Try to emulate such a successful and elegant theory!
In fact, it was a bit too human for my taste. One thing that really struck me as human chauvinistic bravado, reminiscent of Penrose-style crackpotness, was the following passage (top of p.11)
"One (psychological) reason people feel that P=NP is unlikely, is that tasks as above often require a degree of creativity which we don't expect a simple computer program to have. We admire Wiles' proof of Fermat's Last Theorem ... because they seem to require a leap which cannot be made by everyone, let alone, by a simple mechanical device. Our intuition rebels against the possibility that finding solutions is always as easy as verifying them. Indeed, we would argue that a fair intuitive translation of the P vs. NP problem is can creativity be automated?, where creativity is taken to be the abundant, verifiable kind."[this kind of emphasis is mine, this kind of emphasis is in the original].
Now, my dear Avi, first whom are you calling "simple mechanical devices?". Even today's computers are not that simple, and human-beings are not as complex as you think. Besides, I have news for you. "Creativity" (whatever that means) is already starting to be automated, and very soon automated creativity will surpass that of humans, but nevertheless, P is not NP. What is "creativity" anyway?, it is nothing but the use of heuristic (probabilistic) quasi-algorithms programmed by Mother Nature to us so-called humans (with some models better than others). Once computers will learn to "cheat" and use these quasi-algorithms as opposed to full-fledged algorithms, the tiny edge that humans still have over machine-kind will evaporate.
Also you make too much of a big deal of "easy to certify" but "hard to find". It is true that the class of NP-hard problems are (most probably) hard, but the fact that they are easy to check is peripheral, and does not shed any light on why they are indeed hard.
Also one should not overstate the fact that there are "thousands of different problems that are NP-complete, and it is too good to be true that all of them are easy". All the problems in, say, Garey and Johnson, are essentially one problem, since they are all trivially equivalent. Suppose that before Cardano, they would have noticed that if x3+2x+1=0 is solvable by radicals, then so would (2x)3+2(2x)+1=0, (3x)3+2(3x)+1=0, (4x)3+2(4x)+1=0, ... ad infinitum, be solvable by radicals, and it is extremely unlikely that they all can be thus solved, and hence we have strong heuristic support that x3+2x+1=0 is not solvable by radicals. In that case, of course, all that "intuition" would have been wrong. Now if you did the analogous thing for x5+2x+1=0 before Abel and Galois, then the intuition would have been correct, but for the wrong reason.
You admit that using polynomial-time as a benchmark was chosen in part because it is convenient, and that all you care about is asymptotics. This seems to assume that the universe is arranged for our epistemological convenience. This may be the right paradigm for sorting and other garden-variety tasks, but I don't buy the fact that because "very few known efficient algorithms for natural problems have exponents above 3 and 4", it is the right paradigm. We are stupid and limited humans and the empirical evidence is very skimpy. Besides, it is easy to construct natural polynomial-time algorithms of arbitrary exponent by taking a two-parameter family (e.g. finding a clique of size k in an n-vertex graph), that is O(nk). Asymptotic theories are suspect since they talk about infinity, and let me remind you that the world (both physical and mathematical) is finite. Of course, one can still make sense of "asymptotic" statements by talking about "symbolic n", and the reason that, say, heap-sort is O(nlog(n)) is because the running time T(n) (for symbolic(!) n) satisfies a certain divide-and-conquer recurrence that can be solved for symbolic(!) n, yielding O(n log n).
Speaking of symbolic n, this is another misunderstanding, about "proof systems". I am not impressed by the huge lower bounds on numerical pigeon-hole. The pigeon-hole principle is trivial when there are n+1 pigeons and n pigeon-holes for symbolic n, and making it numeric is kind-of-artificial.
Also all the major outstanding open problems in mathematics do not fit into the asymptotic framework. As you say yourself, RH (and P vs. NP, and Goldbach, and 3n+1, etc.) are just one problem at a time, and introducing a parameter n (say that the sum of the mobius function from 1 to n is less than C(eps)*n(.5+eps)) is not just "not useful" but completely misleading. RH, Goldbach, and P vs. NP are each one statement, and their proofs, if they exist (and I am sure that they do) have each complexity O(1). In other words it is just a mere constant, that you, with your asymptotic snobbery, so despise! The example that you cite about the equivalence of certain diophantine equations and knots only show that neither problems were good ones, and the insight gained, if any, is of the negative kind.
Let me end-up by stating my views of why P is most probably not equal to NP, and why it would be so hard to prove that fact.
Now, why is it so hard for us to prove the "intuitively obvious" fact that SAT is not in P? The main reason is because it is intuitively obvious. As we all know, those "intuitively obvious" statements are often the most difficult nuts to crack. Goldbach and the twin primes are intuitively obvious, and even RH. Even more intuitively obvious are the facts that Zeta(5) and e+pi are irrational numbers, because why should they be rational? There are aleph real numbers but only aleph zero rational numbers, so unless there is an obvious reason (like the infinite series Sum(1/(n(n+1)),n=1..infinity) that is telescoping), they are most likely irrational (and even transcendental). Now try to prove that! That's a different matter, and the reason it is so hard, is that you are mixing apples and oranges. It is very artificial to assume that pi+e is an algebraic number (and try to arrive at a contradiction), since the natural definition of pi+e has nothing to do with the notion of being algebraic.
I do believe that there exists a proof that P is not NP, and its complexity is O(1) [of course it can't be O(exp(n)) or even O(log(n)) since it is just one problem], but the "implied constant" is huge! In other words, the proof exists but is very very long [hopefully not too long for our physical universe, to paraphrase Pierre Cartier's suggestion about the possible inconsistency proof of set theory]. There is no hope, as smart and "creative" as you and your cronies are, that you will be able to prove it by yourselves. Your only hope is to enlist that "simple" mechanical device, that ironically, you computer-scientists, do not use very much, not even for spell-checking! (or else you would have been grateful rather than greatful to all those people listed at the end of of your talk, and Vandermunde would have been Vandermonde). But forget about spell-checking. Leaving a few typos (intentionally if necessary) makes for a friendlier expose. On the other hand, if you ever hope to make significant progress in your holy grail, as opposed to just proving yet-another reduction theorem, then you should start to actually use the computer -non-trivially and "creatively" (whatever that means)- rather than just prove theorems about it, and focus on symbolic computation as opposed to mere numeric computation.