Historical dossier 052

On the 1st of April 2009, Doron Zeilberger proved that P is equal to NP.

A recorded P = NP claim by Doron Zeilberger, preserved from Woeginger’s frozen 2016 page.

Dossier: 052
Author(s): Doron Zeilberger
Date recorded: 1st of April 2009
Direction: P = NP
Works or versions: 1
Adjudication: Recorded
Seed source: sources/captures/woeginger-list-frozen-2016.html
Source selector: ol > li:nth-of-type(52)

Woeginger’s note — verbatim historical text

Verbatim historical text

[Equal]: On the 1st of April 2009, Doron Zeilberger proved that P is equal to NP. He provided a polynomial time algorithm for the Subset Sum problem. Zeilberger translates the problem into evaluating an underlying integral. He writes: "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." The paper can be found at http://www.math.rutgers.edu/~zeilberg/mamarim/mamarimPDF/pnp.pdf. At the end of April 2009, Doron Zeilberger wrote me: [...] However, you should add that this was meant as an April Fool's Joke, since apparently, some people didn't get that it was meant as a joke, and while the paper has some valid general statements abouts humans, the "proof" itself is complete gibberish (and of course, intentionally so). (Thanks to Fred Wehrung for providing this link.)

Preserved from the frozen 2016 page. This is the historical layer, not the Register’s voice.

Adjudication status

Adjudication recorded

Recorded

This historical dossier records an adjudication in Woeginger’s note. Follow the sources in that note for its basis. The Register has not re-judged it.

As of 24 July 2026

Links printed in the dossier

Link status checked against the held 24 July 2026 probe. A dead link does not change the claim’s status.

Link printed in the historical dossier
Live
http://www.math.rutgers.edu/~zeilberg/mamarim/mamarimPDF/pnp.pdf
200 · Link status checked 24 July 2026.

Cite this dossier

Plain text

The P versus NP Register. “Dossier 052: On the 1st of April 2009, Doron Zeilberger proved that P is equal to NP..” As of 24 July 2026.

BibTeX

@misc{pvnp-register-052-2026,
  author = {{The P versus NP Register}},
  title = {On the 1st of April 2009, Doron Zeilberger proved that P is equal to NP.},
  year = {2026},
  note = {Dossier 052; as of 2026-07-24}
}

Event timeline

No post-seed events are recorded for this dossier. Its imported historical record remains unchanged.