Printed Name:________________________________________

"On my honor, as an Aggie, I have neither given nor received unauthorized aid on this academic work. In particular, I certify that I have not received or given any assistance that is contrary to the letter or the spirit of the collaboration guidelines for this assignment."

Signature:___________________________________________

1. (2 pts) Suppose you know that the Hamiltonian cycle problem (HC) is NP-complete and you need to prove that the vertex cover problem (VC) is NP-complete. You need to show that there is a reduction from one of these problems to the other. Which way should the reduction go: given any HC input, construct a VC input, OR given any VC input, construct a HC input?
   
   
   
   
   
   
2. (2 pts) Suppose f is a polynomial reduction from the traveling salesman problem (TSP) to the 3SAT problem. So given a TSP input x, f produces a 3SAT input f(x). Which of the following relationships must hold between x and f(x)? Choose one.
   • (a) No required relationship
   • (b) if x has a tour of the given length, then f(x) is satisfiable
   • (c) if f(x) is satisfiable, then x has a tour of the given length
   • (d) both (b) and (c)
   
   
   
   
   
3. (1 pts) True or False: Suppose we know that there is a polynomial reduction from problem P1 to problem P2. If there is a polynomial-time algorithm for P1, then there is a polynomial-time algorithm for P2.