# 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).

We will follow the template given in an earlier post.

## Problem Statement

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

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:

$Ax \le b$ Note: We define $$\le$$ for vectors $$u, v$$ with length $$n$$ as $$u \le v \iff \forall i : 1 \le i \le n: u_i \le v_i$$. In other words, $$u$$ is element-wise less or equal to $$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 0-1 integer programming is NP hard by showing:

$\text{3-CNF-SAT} \le_\text{P} \text{0-1-Integer-Programming}$

### Reduction

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

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

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

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

In other words: $$b_i = -1~$$ plus 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:

$x_i = \begin{cases} 1~&\text{if variable}~i~\text{is assigned True}\\ 0~&\text{if variable}~i~\text{is assigned False} \end{cases}$

Let $$y = Ax$$, then:

$y_i \leq b_i \iff \text{sum of satisfied literals in clause}~i \geq 1 \iff \text{clause}~i~\text{is satisfied}$

From this equation:

$y = Ax \leq b \iff x~\text{is an assignment satisfying}~\Phi$

Thus we have expressed a 3-CNF-SAT problem as a 0-1 integer programming problem. $$\blacksquare$$

### Example

I think it’s much easier to get intuition for this reduction by looking at an example, so here it is:

$\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)$

Our reduced instance looks as follows (zeroes omitted):

$\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}$

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

$\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}$