There are polynomial-time algorithms (in particular, Khachiyan's ellipsoid algorithm) to solve any linear program (LP). (By "solve" we mean here either to find an optimum vector "x" or merely to decide whether the feasible region is nonempty: these problems are easily poly-time reducible to each other.) Say that matrix A and vectors b, c are integer if all their entries are integer. An integer triple (A, b, c) defines an LP in standard form (maximize c^x s.t. Ax lessthanorequalto b) (providing the dimensions match appropriately): but it can also be regarded as defining an integer linear program (ILP), in which we make the additional requirement that the solution vector x is integer. (a) Show that an LP defined by integer (A, b, c) may have a unique optimum at x which is not integer, and for which c^x is not integer. (b) Say that ILP (A, b) is feasible if there exists an integer x satisfying all the inequalities b_i greaterthanorequalto A_i x, where A_i denotes the ith row of A. (Notice, we've omitted "c" because we care only about feasibility.) Show that ILP feasibility is an NP-complete problem. For the NP-hardness, reduce from Vertex Cover