Question

Show Integer Programming is NP-complete.

Answer 1

Integer linear programming (ILP) is like linear programming, with the
additional constraint that all variables must take on integral values.
The decision version of integer programming asks whether or not there
exists a point satisfying all the constraints (for the decision
version there is no objective function).

Claim: ILP is NP-complete.

Proof:

(1) ILP is in NP.

(2) We can reduce 3SAT to ILP:

Let the variables in the 3SAT formula be x_1, x_2, ..., x_n.  We will
have corresponding variables z_1, z_2, ..., z_n in our integer linear
program.  First, restrict each variable to be 0 or 1:

0 <= z_i <= 1       for all i

Assigning z_i=1 in the integer program represents setting x_i=true in
the formula, and assigning z_i=0 represents setting 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.

To satisfy this inequality we must either set z_1=1 or z_2=0 or z_3=1,
which means we either set x_1=true or x_2=false or x_3=true in the
corresponding truth assignment.