Computer Science Stack Exchange is a question and answer site for students, researchers and practitioners of computer science. It's 100% free, no registration required.

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

In 2009 Doron has published a paper stating "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.". I've been looking for other people's opinions on this but I haven't found anything significant. Has this problem been officially settled? is this a correct solution? I am not able to assess the paper because of my limited knowledge. What do you guys think ?

Paper :

share|cite|improve this question
The footnote gives the date the paper was written: April 1 2009. – Nicholas Mancuso Feb 20 '13 at 5:22
@NicholasMancuso I wasn't aware of "April fools", but it seems like its a hoax. Thanks! – Mike G Feb 20 '13 at 5:24
The html "cover page" has an explicit exclamation after the publication date. If you look at the cover page of the Personal Journal, you will find many more issues that were solved on April 1: R(n,n) IS LESS THAN A CONSTANT TIMES (3.9999999999999997)**n, Proof of the Celebrated Goldbach's Theorem, The Mathematics Behind the Proposed Reform of the Hebrew Calendar, Mathematical Genitalysis: A Powerful New Combinatorial Theory that Obviates Mathematical Analysis, Research Announcement: The Transcendence of e+Pi and e*Pi. – Hendrik Jan Feb 20 '13 at 11:44
Just look at the remark in the end... :) – Juho Feb 20 '13 at 15:15
up vote 10 down vote accepted

That paper is a hoax. If you look, it just throws numbers around for a huge polynomial bound, purports to solve a problem by "Laurent polynomials" without any clue on how they relate to the problem, shifts to integrals and estimates them by numerical means "sufficiently precisely" (and that is supposed to give the huge degree polynomial somehow). And nowhere are the 3000 hours of CRAY time to be seen.

share|cite|improve this answer
It was hard to tell since he is a known mathematician and it is hosted on his website. Thanks for clarifying! – Mike G Feb 20 '13 at 5:23
Mathematicians are pranksters too... Knuth's introduction to his monumental "The Art of Computer Programing" sports a quote on following instructions exactly and getting fine results... taken from a cookbook. – vonbrand Feb 20 '13 at 5:26
And also Dr. Z. is not your standard mathematician either :) – Sasho Nikolov Feb 20 '13 at 23:46
@SashoNikolov, the above average mathematicians I've met weren't precisely "standard", so perhaps he is a bog standard mathematician... ;-) – vonbrand Feb 21 '13 at 0:12
doron has a very funky writing style that is as close as a real mathematician can come to writing like a crank. incl many opinionated blog articles, crediting a imaginary pseudonymous coauthor in real papers. etc., recent article. see eg intro to proof of the alternating sign conjecture – vzn Mar 9 '13 at 6:16

It is a sort of joke CS or Google IQ test. It's usually worth checking the semi-official "crank" list for these types of proofs maintained by Woeginger.

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

share|cite|improve this answer

Your Answer


By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.