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
(
Read more... )