Answer Happy

Question 3: Show that the following problems are in NP (this does not contains the harder part of showing that the problem is NPC. You only need to show that given a candidate solution, it is possible to check in polynomial time if the solution is valid). 1. Given an set of numbers S and a target T, the question is if there a subset S'CS whose numbers sum to exactly T. 2. The k-coloring problem. Given a graph and an input k (k can depend on n) is the graph k-colorable? 3. Given a graph G(V. E), a number k and a number t. Is there a subset U of V of size Uk so that the number of edges with both endpoints in U is at least t? 4. Given a universe U, a collection of subsets S₁, S₂,..., Sm of U and a number k, is there a subcollection S₁,S₁, whose union is U? Namely U = U₁1 Si,.