0-1 Integer Programming (0-1 INT). Given a matrix A and a vector b, is there a vector x with values from {0, 1} such that Ax ³ b?

If we did not require the vector x to have integer values, then this is the linear programming problem and is solvable in polynomial time. This one is more difficult.

Theorem 2. 0-1 INT is NP-complete.

Proof. As usual it is easy to show that 0-1 INT is in NP. Just guess the values in x and multiply it out. (The exact degree of the polynomial in the time bound is left as an exercise.)

A reduction from 3-SAT finishes the proof. In order to develop the mapping from clauses to a matrix we must change a problem in logic into an exercise in arithmetic. Examine the following chart. It is just a spreadsheet with values for the variables x₁, x₂, and x₃ and values for some expressions formed from them.

Expressions	Values
X1	0	0	0	0	1	1	1	1
X2	0	0	1	1	0	0	1	1
X3	0	1	0	1	0	1	0	1
+ X1 + X2 + X3	0	1	1	2	1	2	2	3
+ X1 + X2 - X3	0	-1	1	0	1	0	2	1
+ X1 - X2 - X3	0	-1	-1	-2	1	0	0	-1
- X1 - X2 - X3	0	-1	-1	-2	-1	-2	-2	-3

Above is a table of values for arithmetic expressions. Now we shall interpret the expressions in a logical framework. Let the plus signs mean true and the minus signs mean false. Place or's between the variables. So, +x₁ + x₂ - x₃ now means that

x₁ is true, or x₂ is true, or x₃ is false.

If 1 denotes true and 0 means false, then we could read the expression as x₁=1 or x₂=1 or x₃=0.

Now note that in each row headed by an arithmetic expression there is a minimum value and it occurs exactly once. Find exactly which column contains this minimum value. The first expression row has a zero in the column where each x_i is also zero. Look at the expression. Recall that +x₁ + x₂ + x₃ means that at least one of the x_ishould have the value 1. So, the minimum value occurs when the expression is not satisfied.

Look at the row headed by +x₁ - x₂ - x₃ . This expression means that x₁ should be a 1 or one of the others should be 0. In the column containing the minimum value this is again not the case.

The points to remember now for each expression row are:

a) Each has exactly one column of minimum value.
b) This column corresponds to a nonsatisfying truth assignment.
c) Every other column satisfies the expression.
d) All other columnms have higher values.

Here is how we build a matrix from a set of clauses. First let the columns of the matrix correspond to the variables from the clauses. The rows of the matrix represent the clauses - one row for each one. For each clause, put a 1 under each variable which is not complemented and a -1 under those that are. Fill in the rest of the row with zeros. Or we could say:

The vector b is merely made up of the appropriate minimum values plus one from the above chart. In other words:

b_i = 1 - (the number of complemented variables in clause i).

The above chart provides the needed ammunition for the proof that our construction is correct. The proper vector x is merely the truth assignment to the variables which satisfies all of the clauses. If there is such a truth assignment then each value in the vector Ax will indeed be greater than the minimum value in the appropriate chart column.

If a 0-1 valued vector x does exist such that Ax ³ b, then it from the chart we can easily see that it is a truth assignment for the variables which satisfies each and every clause. If not, then one of the values of the Ax vector will always be less than the corresponding value in b. This means that the that at least one clause is not satisfied for any truth assignment. 

Here is a quick example. If we have the three clauses:

then according to the above algorithm we build A and b as follows.

Note that everything comes out fine if the proper values for the x_i are put in place. If x₃ is 0 then the first entry of Ax cannot come out less than 0 nor can the second ever be below -1. And if either x₂ or x₁ is 1 then the third entry will be at least 1.