3. NP (9 points)

Prove that each of following problems:

Show that it is in NP by sketching a polynomial time verifier for it.

Show that each problem is NP-hard by giving a polynomial time reduction

from a known NP-complete problem to the one in question.

(3) HALF-SUBSET = {S,t | S = {x1,...,xn} is a set of positive num- k

bers such there exists a set {y1,...,yk} S where yi = t and k n/2 i=1

(i.e., we use less than half the numbers in S to get t) }

Hint: Try reducing from SUBSET-SUM. Add extra numbers to S which you know dont change whether a subset of S adds up to t. Since S is a set your numbers must all be different from each other and from ones already in the set.