Cheap and Secure Web Hosting Provider : See Now

[Solved]: Mistake in Karp's paper on NP-Complete problems?

, , No Comments
Problem Detail: 

I read on a blog that there are mistakes in Karp's paper where he proved that 0-1 programming is NP-Complete, but I couldn't find it, can anyone explain? And I doubt that there are also mistakes where he proved Steiner Tree Problem is NP-Compelete but not sure.

The blog post a little old and I thought asking the writer of the blog may not receive answer quickly enough. I didn't find any referrence in other places so I thought this question may worth asking.

Asked By : sjtufs

Answered By : Raphael

To cite the blog post:

For arguments sake, lets say that in Karp's classic paper Reducibility Among Combinatorial Problems, where he proves 21 problems NP-compete, he made a mistake on 0-1 programming.

That is, the blog author does not state that there is a mistake. It is just a gedankenexperiment.

That is, of course, not to say that there is none.

Best Answer from StackOverflow

Question Source :

3.2K people like this

 Download Related Notes/Documents


Post a Comment

Let us know your responses and feedback