Proving 0-1 integer programming is NP-complete (using reduction from 3-CNF-SAT)

In this post, we will prove that 0-1 integer programming is NP-complete using a reduction from 3-CNF-SAT (which is NP-complete[1]). We will follow the template given in an earlier post.

Problem statement

The decision problem for 0-1 integer programming is formulated as follows[2]:

Given an integer $m \times n$ matrix $A$ and an integer $m$ -vector $b$ , determine whether there exists an integer $n$ -vector $x$ with elements in $\{0, 1\}$ , such that:

(1) $\begin{equation*}Ax \le b\end{equation*}$

Note: For vectors $u, v ~:~ u \le v \iff$ all elements in $u$ are element-wise less than or equal to all elements in $v$ .

Showing the problem is in NP

Let the certificate be vector $x$ . $Ax$ can be computed in $\mathcal{O}(nm)$ . Finally, elementwise comparison of $Ax$ and $b$ can be performed in $\mathcal{O}(m)$ to determine if $Ax \le b$ . This proves a certificate for the problem can be verified in polynomial time.

Showing the problem is NP-hard

We will show that the problem is NP-hard by showing:

(2) $\begin{equation*}\textsc{3-CNF-SAT} \le_\text{P} \textsc{0-1-Integer-Programming}\end{equation*}$

Reduction

For 3-CNF formula $\Phi$ , containing $v$ variables and $c$ clauses, construct $c \times v$ matrix $A$ such that:

(3) $\begin{equation*}a_{i, j} =\begin{cases}-1~&\text{if variable \textit{j} occurs \textbf{only without negation} in clause \textit{i}}\\1~&\text{if variable \textit{j} occurs \textbf{only with negation} in clause \textit{i}}\\0~&\text{otherwise}\end{cases}\end{equation*}$

Also, construct $c$ -vector $b$ such that:

(4) $\begin{equation*}b_i = -1 + \sum_{j=1}^v \max(0, a_{i, j})\end{equation*}$

In other words: $b_i = -1 +$ the number of negated literals in clause $i$ .

We observe that $A$ and $c$ can be constructed in $\mathcal{O}(cl)$ , proving that the reduction can be done in polynomial time.

We will now prove that the existence of $c$ -vector $x : Ax \le b \iff \Phi$ is satisfiable. Consider vector $x$ to represent an assignment of the variables in $\Phi$ , where:

(5) $\begin{equation*}x_i = \begin{cases}1~&\text{if variable \textit{i} is assigned \textsc{True}}\\0~&\text{if variable \textit{i} is assigned \textsc{False}}\end{cases}\end{equation*}$

Let $y = Ax$ . From Equations 1, 3 and 4:

(6) $\begin{equation*}y_i \leq b_i \iff \text{sum of satisfied literals in clause \textit{i}} \geq 1 \iff \text{clause \textit{i} is satisfied}\end{equation*}$

From Equation 6 and the definition of the $\leq$ operator

(7) $\begin{equation*}y = Ax \leq b \iff x~\text{is an assignment satisfying}~\Phi \qquad \blacksquare\end{equation*}$

Example

(8) $\begin{equation*}\Phi = (x_1 \lor x_2 \lor \lnot x_3) \land (x_1 \lor x_3 \lor x_4) \land (\lnot x_2 \lor \lnot x_3 \lor \lnot x_4) \end{equation*}$

Our reduced instance looks as follows (zeroes omitted):

(9) $\begin{equation*}\begin{bmatrix}-1 & -1 & 1 & \\-1 & & -1& -1 \\ & 1 & 1 & 1 \end{bmatrix}\times\begin{bmatrix}x_1\\x_2\\x_3\\x_4\end{bmatrix}\le\begin{bmatrix}0\\-1\\2\end{bmatrix}\end{equation*}$

We can see that $\langle x_1 = \text{T}, x_2 = \text{F}, x_3 = \text{F}, x_4 = \text{F}\rangle$ satisfies $\Phi$ and that

(10) $\begin{equation*} \begin{bmatrix} -1 & -1 & 1 & \\ -1 & & -1& -1 \\ & 1 & 1 & 1 \end{bmatrix} \times \begin{bmatrix} 1\\ 0\\ 0\\ 0 \end{bmatrix}=\begin{bmatrix} -1\\ -1\\ 0 \end{bmatrix} \le \begin{bmatrix} 0\\ -1\\ 2 \end{bmatrix} \end{equation*}$

[1]
R. M. Karp, “Reducibility among Combinatorial Problems,” in Complexity of Computer Computations, Springer US, 1972, pp. 85–103.
[2]
T. H. Cormen, C. E. Leiserson, R. L. Rivest, and C. Stein, Introduction to Algorithms. MIT Press, 2009.