CISC 3220 - Homework #9

Due: Wednesday, Dec. 14.

1. Define the class P and the class NP.



2. Prove that the following problems (which we defined in class) are in the Class NP. (Recall that in order to prove that a problem is in NP you must show a polynomial time algorithm to verify a solution.)
   1. TSP (Travelling Salesperson Problem)
   2. Subset Sum
   3. Hamiltonian Cycle



3. State whether the following set relations are TRUE, FALSE, or UNKNOWN.
   1. P is a subset of NP
   2. NP is a subset of P
   3. P is a proper subset of NP
   4. NP-Complete is a subset of NP
   5. NP-Complete is a proper subset of NP
   6. The intersection of P and NP-Complete is empty.