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.