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.

(1) TWO-SOLUTIONS = {F | F is a boolean formula which is satisfied

by two different assignments of truth values to your variables}

Hint: Try reducing from 3SAT and keep in mind that the formulas in TWO-SOLUTIONS are not required to be in 3cnf (this fact should make the reduction easier).

(2) LPATH = {G,s,t,k | G is an undirected graph with a simple path from s to t with length at least k}

Hint: A simple path has no repeated nodes. Try reducing from UHAMPATH = {G,s,t | G is an undirected graph with a Hamilto- nian path from s to t}.

(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.