Opinion 45: The Clay Mathematics Institute Should Pay Most of the Million-Dollar Prize to the Anonymous Genius Who Proved that the P vs. NP Problem is NP Hard

By Doron Zeilberger

Written: April 1, 2002 (!)

Every mathematician is trying to solve at least one of the seven notorious million-dollar Clay Mathematics Institute Millennium problems, although no one would admit it. Of course, it is not the money per se, since we mathematicians and theoretical computer scientists care very little about such trivial and undignified things as money. Instead it is the pure and noble search for insight and understanding, and the `money' is just a virtual token, like Erdos's checks that never got cashed.

The problem with the Clay problems is that they are prejudiced towards the so called `rigorous' mathematical proof-standards, implicitly excluding many other much more creative, and intrinsically just as legitimate, methods of reasoning used in the physical and social sciences, plus future non-Fregean logics. The Clay Institute is also very elitist, insisting that the articles be published in `refereed mathematical journals of world-wide repute'. Who is to decide how reputable a journal is? It would be nice if they provided a list, so that I would know where to submit my forthcoming proof of the Riemann Hypothesis.

But besides the Clay Institute's implicit snobbism and pecuniary contamination of pure math , in line with the disgusting capitalistic reductionism of everything (including misery and even death) to dollars, there are even more fundamental issues, epitomized by the recent (`secret', but, paraphrasing Professor Dumbledore, `so naturally the whole mathematical world knows') approach by the brilliant Russian-American high-school student, let's call her X, to the P vs. NP problem. Even though it is supposed to be secret while X's law-suit against the Clay Institute is still pending, I believe that we should all write anonymous letters of protest to the Clay Institute and to the Press, in support of X's claims for the million-dollar prize, or at least for a large part of it.

The first excuse of the Clay `Advisory' Board Committee is that Ms. X's solution was submitted directly to them, and not to a `reputable math journal'. This is very unfair, since X's approach is such a revolutionary paradigm shift, that it has no chance of being published in an orthodox math journal. On the other hand, her breakthrough article was eagerly accepted by Physical Review Letters (since she uses `non-rigorous' but highly effective methods from Quantum Field Theory, like Renormalization Groups, Feynman Integrals, Feynman diagrams, and simulated annealing), and the `Electronic Journal of Mathematical Software', since her approach uses 1000 hours of computer-time running a very sophisticated computer program.

The second excuse of the Clay `Institute' is that Ms. X did not settle the P vs. NP problem, neither affirmatively nor negatively, nor even undecidably. `All she did', said Clay's council in court, was `to use non-rigorous crazy (sic) methods from physics, using error-prone computer calculations, to estimate lower bounds for the length of a formal proof that P is not NP, should it exist'. Her lower bounds (which are probably still an underestimate compared to the truth) are astronomical:10**(10**1000) GB.

In my humble opinion, X's breakthrough is far more interesting than a mundane `rigorous mathematical proof' of P<>NP would have been. She proved (by very legitimate methods recognized as valid by all scientists except pedantic and narrow-minded mathematicians) that there is NO proof. At least, not in THIS Universe, since such a proof, it if exists, will require memory-space the size of zillions of universes, and computer time equal to zillions of big-bangs.

It is very possible that her approach will extend to the six other Millennium problems, hence showing the humbugness of the `prizes'. Perhaps they should also offer a prize for squaring the circle and doubling the cube? Hello!, these are impossible (the latter two in principle, the former six in practice), hence it is safe for Mr. and Mrs. Clay to offer big prizes!, and get cheap publicity that they would never have to pay for.

There is already a precedence for awarding a prize for a breakthrough on a problem, even though it was not solved in the intended way. The King of Sweden decided to award Poincare the prize for `a closed-form solution of the three-body problem', even though Poincare didn't actually solve it, but rather proved its ergodicity and its chaotic behavior.

The Clay Institute should follow King Oscar II's example, forget its traditional mathematical hang-ups, and award the P vs. NP prize to Ms. X immediately, or at the very least, 999,999.99 dollars. They can deduct 1 cent as a token concession to old-timers who are still stuck in the obsolete Euclidean and Fregean `absolute certainty' frame of mind.


Doron Zeilberger's Opinion's Table of Content

Doron Zeilberger's Homepage