Home /
Expert Answers /
Computer Science /
4-15-points-given-an-integer-mn-matrix-a-and-an-integer-m-vector-b-the-feasible-0-1-integer-pa164

4. [15 POINTS] Given an integer $m×n$ matrix $A$ and an integer $m$-vector $b$, the feasible 0-1 integer-programming problem (feasible 0-1-IP or simply just 0-1-IP) asks whether there exists an $n$-vector $x$ with elements in the set ${0,1}$ such that $Ax?b$. (a) (5 pts) Show that 0-1-IP is in NP. Be sure to clearly specify a set of certificates, along with a polynomial time verification algorithm for 0-1-IP. You must establish the correctness and polynomial time bound of your verification algorithm. (b) (9 pts) Show that $3?CNF?SAT?_{P}$ 0-1-IP. Be sure to clearly specify your reduction, and to establish its correctness. (c) (1 pt) Show that 0-1-IP is NP-complete.

(a) To show that 0-1-IP is in NP, we need to show that given an instance of the problem and a proposed solution, we can verify the solution in polynom