1. (Sipser Exercise 7.44) Show that UNARY-SUBSET-SUM is in P.
2. (Sipser Exercise 7.6) Show that P is closed under union (Intersection -- do this later), concatenation, (complement -- do this later).
3*. (Sipser Exercise 7.42) Show that P is closed under Kleene star. (Hint: dynamic programming)
4. (Sipser Exercise 7.7) Show that NP is closed under union and concatenation. Try to use non-determinism.
5. (Sipser Exercise 7.43) Show that NP is closed under Kleene star. (Hint: Use non-determinism)
6. (Sipser Exercise 7.45) Suppose P=NP. Let A be any non-trivial language (neither A nor its complement is empty). Show that A must NP-complete. (Hint: Pay attention to the definition of <=m reductions.)