Spots on the Sun (Richard M. Karp and NP-complete problems)
It seems that reduction SAT to 0-1 programming in famous paper "Reducibility Among Combinatorial Problems" (1972) by Richard M. Karp contains a mistake. Let we have a simple formula of 1 clause: (x V y V z). Following the Karp's reduction, we will get the equation x + y + z = 1, which is not eqivalent to the source boolean formula, However the unequality x + y + x >= 1 is equivalent.
However, it seems, it is a well known point:
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. The problem IS NP-complete and the correct proof is in many textbooks (also, anyone reading this blog can probably do it themselves). Is it worth wasting Karp's time with this? (From here https://blog.computationalcomplexity.org/2011/10/if-you-find-mistake-in-someone-elses.html )
However, it seems, it is a well known point:
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. The problem IS NP-complete and the correct proof is in many textbooks (also, anyone reading this blog can probably do it themselves). Is it worth wasting Karp's time with this? (From here https://blog.computationalcomplexity.org/2011/10/if-you-find-mistake-in-someone-elses.html )