patternMinor
0/1 Integer Programming and Karp's Reduction
Viewed 0 times
programmingreductionandintegerkarp
Problem
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?
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?
Solution
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.
Context
StackExchange Computer Science Q#19716, answer score: 5
Revisions (0)
No revisions yet.