0/1 Integer Programming and Karp's Reduction

Question

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?

• Yonatan N: 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.
• john_leo: 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.

Answer 1

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.