Problem Detail: 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?
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?
Asked By : john_leo
Answered By : 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.
Best Answer from StackOverflow
Question Source : http://cs.stackexchange.com/questions/19716
