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 elementof N, c is an integer vector of length m, and there exists x elementof {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 Ls NP-complete.

Solution

Proof:
We know that (0-1)Intger Programming is in NP.
We also know that we can reduce 3SAT to (0-1)Intger Programming:

Let the variables in the 3SAT formula be
x_1, x_2, ..., x_n.
and the corresponding variables z_1, z_2, ..., z_n in (0-1)Intger Programming . First, we restrict each variable to be 0 or 1:

0 <= z_i <= 1   for all i

Assigning z_i=1 in the integer program represents x_i=true
whereas z_i=0 represents x_i=false.

For each clause like (x_1 OR not(x_2) OR x_3), have a constraint like:

z_1 + (1-z_2) + z_3 > 0.

SO to satisfy this inequality
we must set z_1=1 or
z_2=0 or
z_3=1,
which means we set
x_1=true or
x_2=false or
x_3=true in the
Hence prooved that (0-1)Intger Programming is NP-complete.