Research Announcement: A Computer-Generated Proof that P=NP

Doron ZEILBERGER^{1}

Abstract: Using 3000 hours of CPU time on a CRAY machine, we settle the notorious P vs. NP problem in the affirmative, by presenting a “polynomial” time algorithm for the NP-complete subset sum problem. Alas the complexity of our algorithm is O(n^{10^{10000}}) (with the implied constant being larger than the Skewes number). This anticlimatic resolution of the “central” problem in theoretical computer science indicates the fatal flaw of the ruling paradigm in computational complexity theory that equates “polynomial time” with “fast”, and presents yet another cautionary tale about the human propensity to trust artificial and crude models blindly, as witnessed in the recent collapse of Wall Street.

P=NP

Like many solutions of long-standing open problems, the main idea of our solution is tantalizingly simple (by hindsight!). Recall the following NP-complete problem

The Subset Sum problem: Given a set T of integers, and an integer b, decide whether or not there exists a subset S ⊂ T such that

b = ∑_{s∈S} s .

Consider the Laurent polynomial

P (z) = z^{−b} ∏_{t∈T}(1 + z^{t}) .

Obviously the subset problem is affirmative if and only if the constant term of P (z) is > 0. Using Cauchy’s integral formula, this boils down to computing

A(T, b) := \frac{1}{2πi} ∫_{|z|=1} \frac{P (z)}{z} dz.

Making the substitution z = exp(ix), dz = iexp(ix)dx, we can transform this into an integral on [−π, π]

A(T, b) := \frac{1}{2π} ∫_{−π}^{π} P (e^{ix}) dx.

We now use Gaussian quadrature to approximate this integral with an error of < 1. By using a delicate analysis of the error formula, we can find in the “polynomial” time mentioned in the abstract, a number of points N, such that the Gaussian Quadrature with that number of points does indeed have the required error bound. Alas the N (number of points), is huge (but still “polynomial” in the size of the inputs), and using rigorous interval analysis, rather than non-rigorous floatingpoint computations, we can estimate the integral, as well as bound the error, thereby solving the problem in “polynomial” time. The rigorous estimate of the error (crucial to the success of the decision algorithm), involves solving more than ten thousand Linear Programming problems, each with more than one hundred thousand variables. This system was generated automatically and dynamically, using a genetic algorithm and simulated annealing, as well as sophisticated Markov Chains and Bayesian analysis. Of course, we do not guarantee that this is the shortest possible proof, since it was generated by a non-determinstic Turing machine, but it is indeed a fully rigorous proof. The validity of the proof was independently checked by four other computers, running on different platforms and different programming languages.

1 Department of Mathematics, Rutgers University (New Brunswick), Hill Center-Busch Campus, 110 Frelinghuysen

Rd., Piscataway, NJ 08854-8019, USA. zeilberg at math dot rutgers dot edu , http://www.math.rutgers.edu/~zeilberg . Written: April 1(!), 2009.

Remark: A considerable speed-up can be achieved if one uses “analog” computations, namely an analytical balance easily obtained in any chemistry laboratory. First have the computer plot the real and imaginary parts of P (e^{ix}), above −π < x < π, on high-quality paper. Second, print-out these two plots. Third, using scissors, for each of these plots, carefully cut the parts above and below the x-axis. Third, find the difference in weight between the positive and negative parts, and divide by the weight of a unit square. If the sum of the absolute values of the two differences is less than \sqrt{2}/2, then output no, otherwise yes.

Full details will apear elsewhere.