The 0 1integer programming language IP is defined as follows

The (0, 1)-integer programming language IP is defined as follows: IP:= {(A, c): A is an integer m times n matrix for some m, n N, c is an integer vector of length m, and x {0, 1}^n such that Ax lessthanorequalto c (componentwise)}. Prove that the language IP is NP-complete. You may use the fact that the language SOS is NP-complete.

Solution

ANS: Proof that IP is NP-complete when IP is in NP because the integer solution can be used as a witness and can be verified in polynomial time.1 We now prove that IP is NP-hard by reduction from SAT. A SAT instance is described by a set of Boolean variables and clauses. We reduce it to an Integer Programming instance with the same number of variables. In addition, for each variable vi we have the constraints 0 vi 1. For each clause we have a constraint that correspond to it; for example, for the clause v1 v3 v7 in the SAT instance, we have the constraint v1 + (1 v3) + v7 1. Clearly, this reduction can be done in polynomial time. Moreover, it is easy to verify that if the given SAT instance has a satisfying assignment then the corresponding IP instance has an integer solution and vice versa. Although it is NP-complete, one might hope to obtain efficient algorithms for the case where the dimension (i.e., the number of variables) is fixed. For n = 1, it is easy to come up with an efficient solution. However, even for n = 2, this is no longer obvious. In the next section, we describe the celebrated algorithm by Lenstra that solves IP in polynomial time for any fixed dimension n.