Question

Given an integer m × n matrix A and an integer m-vector b, the 0-1 integer-programming problem asks whether there exists an integer n-vector x with elements in the set {0, 1} such that Ax ≤ b. Prove that 0-1 integer programming is NP-complete. (Hint: Reduce from 3-SAT). Please provide detail explanation and steps.

Answer 1

To prove that 0-1 integer programming is NP-complete, we establish that it is in NP and can be reduced from 3-SAT in polynomial time. Verification of a given solution is in polynomial time, and a matrix A and vector b can be constructed to emulate the 3-SAT constraints as linear inequalities, establishing the NP-hardness of 0-1 integer programming.

Step-by-step explanation:

The student has asked to prove that the 0-1 integer programming is NP-complete, and we can do so by reducing from a known NP-complete problem such as 3-SAT. In the 3-SAT problem, we are given a boolean formula in conjunctive normal form where each clause has exactly three literals, and the question is whether there exists a truth assignment to the variables that makes the entire formula true.

To prove that 0-1 integer programming is NP-complete, we need to show two things:

1. 0-1 integer programming is in NP.
2. Any NP problem, such as 3-SAT, can be polynomially reduced to a 0-1 integer programming problem.

For the first point, we observe that if we are given a solution vector x for the integer-programming problem, we can verify in polynomial time whether Ax ≤ b by simply performing the matrix-vector multiplication and comparing the result to b.

For the second point, we need to construct a polynomial-time reduction from 3-SAT to 0-1 integer programming. This is done by constructing a matrix A and vector b in such a way that each clause in the 3-SAT formula corresponds to a row of A and an entry in b. Here's a rough sketch of the procedure:

• For each clause in the 3-SAT formula, create a row in A.
• For each literal in a clause, if the literal is positive, set the corresponding entry in the row of A to 1; if the literal is negated, set the entry to -1.
• Set the corresponding entry of b for each clause to 1, since we want at least one literal in each clause to be true.

With this setup, a solution to the 0-1 integer programming problem corresponds to a truth assignment for the 3-SAT problem, thereby showing that 0-1 integer programming is at least as hard as 3-SAT, completing the proof that it is NP-complete.