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[peoplefeel that P=NP is unlikely, is that tasks as above often require a degree ofcreativitywhich we don't expect asimplecomputer program to have. We admire Wiles' proof of Fermat's Last Theorem ... because theyseemto require a leap which cannot be made by everyone, let alone, by asimple mechanical device.Ourintuition rebels against the possibility that finding solutions isalwaysas easy as verifying them. Indeed, we would argue that a fair intuitive translation of the P vs. NP problem iscan creativity be automated?, where creativity is taken to be the abundant, verifiable kind."

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 x^{3}+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 x^{3}+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 x^{5}+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(n^{k}). 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.

- Life is hard (analogs of "no free lunch" (conservation of energy) and "everything turns to chaos" (2nd law of Thermodynamics) )
- A fool can ask more questions than a wise person can answer.
- It is hard to find a needle in a haystack (and the fact that once found, it is easy to tell that it is indeed a needle, and not a piece of hay, has nothing to do with the fact that it was hard to find it).
- The vast majority of Boolean functions require exponentially many gates (as was first noted by Claude Shannon), the probability that any one specific function (e.g. SAT) will require only polynomially many gates is miniscule. Since there is no obvious reason why it should be polynomial, it is most probably exponential.

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

Added Jan. 11, 2008: Read Scott Aaronson's interesting feedback

Doron Zeilberger's Opinions Table of Content