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.

Comment viewing options

Thank God it was yesterday.

Thank God it was yesterday.

Indeed

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

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.

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

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

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

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.

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.

I'm sure I've seen that

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

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.

Not even that bad an idea

But that only refers to the title. ;-)

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

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.

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