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

## Leave a comment

This site uses Akismet to reduce spam. Learn how your comment data is processed.