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 matrix and an integer -vector , determine whether there exists an integer -vector with elements in , such that:

(1)

Note: For vectors **all** elements in are element-wise less than or equal to all elements in .

### Showing the problem is in NP

Let the certificate be vector . can be computed in . Finally, elementwise comparison of and can be performed in to determine if . 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)

#### Reduction

For 3-CNF formula , containing variables and clauses, construct matrix such that:

(3)

Also, construct -vector such that:

(4)

In other words: the number of negated literals in clause .

We observe that and can be constructed in , proving that the reduction can be done in polynomial time.

We will now prove that the existence of -vector is satisfiable. Consider vector to represent an assignment of the variables in , where:

(5)

Let . From Equations 1, 3 and 4:

(6)

From Equation 6 and the definition of the operator

(7)

#### Example

(8)

Our reduced instance looks as follows (zeroes omitted):

(9)

We can see that satisfies and that

(10)

- [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.