(Solved): 4. [15 POINTS] Given an integer mn matrix A and an integer m-vector b, the feasible 0-1 integer- ...

4. [15 POINTS] Given an integer $m\times 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.