Home

A Computer-Generated Proof that P=NP

Doron Zeilberger announced yesterday that he has proven that P=NP.

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.

The paper is available here and his 98th Opinion is offered as commentary.

By Leon P Smith at 2009-04-02 06:54 | Critiques | Fun | Theory | other blogs | 23712 reads

Comment viewing options

Select your preferred way to display the comments and click "Save settings" to activate your changes.

Thank God it was yesterday.

Thank God it was yesterday.

By Ehud Lamm at Thu, 2009-04-02 06:56 | login or register to post comments

Indeed

I thought it was much too good to pass up...

By Leon P Smith at Thu, 2009-04-02 07:01 | login or register to post comments

Applying my math skillz, two possible solutions to P=NP

Wonders if computer scientists skipped 6th grade algebra, as the possible solutions seem rather straightforward.

Answer one:

P = NP
N = 1
P = 1P
P = P

Answer two:

P = NP
P = ∞
∞ = N∞
∞ = ∞

By Chris Rathman at Thu, 2009-04-02 14:55 | login or register to post comments

Answer three

P = NP
P = 0
0 = N0
0 = 0

With regard to answer two, what if N is an infinitesimal? Then again, maybe non-standard analysis isn't applicable here... gotta keep in mind the suitability of any given model. ;-)

By Leon P Smith at Sat, 2009-04-04 02:35 | login or register to post comments

Interesting optimization

He has a novel optimization at the end of the paper (in the remark) which I haven't seen in any other paper and which I think could be independently useful in other contexts in Computer Science. I will make sure to study it further.

By Josef Svenningsson at Thu, 2009-04-02 16:23 | login or register to post comments

Tradeoffs

That does seem promising, although I fear that this means that computer science students will now need to be educated on such subjects as the specific gravity of ink, and the effect of the speed of a printer on the time complexity of an algorithm. Not to mention a new kind of space complexity, measured in cubic meters.

By Anton van Straaten at Thu, 2009-04-02 17:30 | login or register to post comments

I'm sure I've seen that

I'm sure I've seen that optimization described before. Origin Bell Labs?

By Luke Gorrie at Thu, 2009-04-02 20:58 | login or register to post comments

Was quite amused

that "The validity of the proof was independently checked by four other computers, running on different platforms and different programming languages." Because without that I wouldn't be able to trust the results.

By erich at Thu, 2009-04-02 22:49 | login or register to post comments

Not even that bad an idea

But that only refers to the title. ;-)

By marco at Tue, 2009-04-07 17:41 | login or register to post comments

Actually...

I've been trying to determine exactly where Dr. Z goes wrong in his "proof". The bit about Laurent polynomials is certainly correct, and I'm reasonably confident that the next two integrals are also correct, although I am not good with complex analysis so I still need to understand where the singularities of the Laurent polynomial can be. (Which should be easy for anybody who actually knows what they are doing...)

I'm suspicious that where the paper departs from reality lies somewhere with the Gaussian quadrature: possibly in the time complexity and not necessarily with the mathematics. but I know very little about quadrature, so it might just be my own ignorance.

So, my (very uncertain) belief is that Dr. Z did actually reduce the evaluation of certain classes of integrals to an NP-complete problem. I suppose I should try emailing him and see what he has to say...

By Leon P Smith at Tue, 2009-04-07 18:01 | login or register to post comments

Fully Rigorous

A finite product of meromorphic functions has its singularities among the singularities of the factors, so P(z) has only z=0 as a singularity. Since z^p only contributes to the residue for p=-1, the integral should be right. I think the problem may be that the genetic algorithms and simulated annealing used might not be fully rigorous.

By Matt M at Tue, 2009-04-07 19:26 | login or register to post comments

Re: Fully Rigorous

Well, I don't know much about simulated annealing, although I agree that genetic algorithms don't seem to me to be a good choice for this kind of correctness-critical task.

Speaking in general terms, another issue is that interval arithmetic can fail to produce useful results: however the nice thing is that at least you know that it produced garbage. So at that point it would be rather difficult, though perhaps not impossible, to call your algorithm a "decision algorithm."

By Leon P Smith at Mon, 2009-04-20 19:18 | login or register to post comments