[GMon]

I'm aware that 0-1 integer programming problem is NP-complete, where the problem is stated as: Given some integer matrix A and some integer vector b, determine whether there exists a vector x consisting of 0's and 1's such that Ax >= b. I've seen that 3-CNF SAT is reducible to this problem.

However, here's a slight variant: Given some integer matrix A and some integer vector b, determine whether there exists a vector x consisting of 0's and 2's such that Ax >= b.

I'm wondering whether it's valid to give a proof sketch based on the following: Given the 0-1 integer programming problem instance (Ax ≥ , construct a new vector b′=2b, and use the "magic box" of 0-2 integer programming to find if there exists a vector x′∈{0,2} such that Ax′≥b′, and say that IFF the answer is yes, there exists a vector x∈{0,1} that solves Ax≥b. Is this a valid approach to the proof? Thanks.

[macosxnerd101]

NP-Completeness Proofs have two parts- showing the problem is in NP and showing it is NP-Hard. To show 0-2 ILP is in NP, provide a polynomial time verification procedure given the instance (A, b) and a certificate- in this case, a satisfying vector x.

To show NP-Hardness, you generally reduce from an existing NP-Hard problem (though there are other techniques). In this case, you are proposing reducing 0-1 ILP to 0-2 ILP. So given (A, b) \in 0-1 ILP, construct an instance of 0-2 ILP (A', b') s.t. (A, b) has a solution iff (A', b') has a solution. You then have to argue that your reduction is correct and computable in polynomial time. There is no "black box" here. You are showing a subset of 0-2 ILP problems are NP-Complete, which implies the entire set 0-2 ILP is NP-Complete.

Your rough idea is generally correct, but be careful about how you structure your NP-Completeness proofs. You have to be exacting about what you are showing. And to do that, you need to understand the conditions that need to be satisfied.