I have been reading Karp's famous paper on the NP-Completeness of different problems, Reducibility among combinatorial problems, and I have a question on the reduction from SAT to 0/1 Integer Programming defined there.

The problem 0/1 Integer Programming is defined as:
Input: Integer matrix $A$ and integer vector $d$
Property: There exists a 0/1 vector $x$ such that $Ax=b$.
Let $B$ be a boolean formula in CNF with $p$ variables $x_1,\dots, x_p$ and $n$ clauses $C_1,\dots,C_n$. The reduction from SAT should work like this ($C_i$ is the $i^{\text{th}}$ clause of the boolean formula): $$ a_{ij} = \begin{cases} 1 &\text{if } x_j \in C_i \\ -1 &\text{if } \bar{x}_j \in C_i\\ 0 &\text{otherwise} \end{cases} $$ and $$ b_i = 1- (\text{ the number of complemented variables in } C_i ). $$ Now if I use this procedure on the satisfiable formula $(x_1 \vee x_2 ) \wedge (x_1 \vee x_3 ) \wedge (x_2 \vee x_3 )$, I get $$ A =\left( \begin{array}{ccc} 1 & 1 & 0 \\ 1 & 0 & 1 \\ 0 & 1 & 1 \end{array} \right), \text{ and } b = \left( \begin{array}{c} 1 \\ 1 \\ 1 \end{array} \right), $$ which has no 0/1 solution. So my question is:
Have I made a very silly mistake, or is Karp's original reduction faulty?

  • I believe there's a typo in Karp's definition of the problem. If we replace $Ax = b$ with $Ax \geq b$, the reduction goes through as is. The easiest way I can think of to show the hardness of your problem (the one as written in Karp's paper), is via 1-in-3 SAT or via hypergraph perfect matching. – Yonatan N Jan 14 '14 at 22:56
  • Hm. Sounds reasonable, I guess it's just that typo. If you want to you can turn your comment to an answer and I can accept it. – john_leo Jan 16 '14 at 10:04
up vote 5 down vote accepted

I believe there's a typo in Karp's definition of the problem. If we replace $Ax=b$ with $Ax \geq b$, the reduction goes through as is. The easiest way I can think of to show the hardness of your problem (the one as written in Karp's paper), is via 1-in-3 SAT or via hypergraph perfect matching.

Your Answer

 
discard

By clicking "Post Your Answer", you acknowledge that you have read our updated terms of service, privacy policy and cookie policy, and that your continued use of the website is subject to these policies.

Not the answer you're looking for? Browse other questions tagged or ask your own question.