## Description

- 1.
*(6 pts)*Let X and Y be two decision problem Suppose we know that X reduces to Y in polynomial time. Which of the following can we infer? Give a YES/NO answer.

- a. If Y is NP-complete then so is X. b. If X is NP-complete then so is Y.
- c. If Y is NP-complete and X is in NP then X is NP-compl

- d. If X is NP-complete and Y is in NP then Y is NP-compl e. If X is in P, then Y is in P.
- f. If Y is in P, then X is in P.

- 2.
*(4 pts)*Consider the problem COMPOSITE: given an integer*y*, does*y*have any factors other than one and itself? For this exercise, you may assume that COMPOSITE is in NP, and you will be comparing it to the well-known NP-complete problem SUBSET-SUM: given a set S of*n*integers and an integer target*t*, is there a subset of*S*whose sum is exactly*t*? Clearly explain whether or not each of the following statements follows from that fact that COMPOSITE is in NP and SUBSET -SUM is NP-complete:

- a. SUBSET-SUM ≤p COMPOSITE.

- b. If there is an
*O*(*n*3) algorithm for SUBSET-SUM, then there is a polynomial time algorithm f or

COMPOSITE.

- c. If there is a polynomial algorithm for COMPOSITE, then P = NP.

- d. If P ¹ NP, then
problem in NP can be solved in polynomial tim*no*

- 3.
*(8 pts)*A Hamiltonian path in a graph is a simple path that visits every vertex exactly onc Prove that HAM-PATH = { (G, u, v ): there is a Hamiltonian path from u to v in G } is NP-complete. You may use the fact that HAM-CYCLE is NP-complete.

- 4.
*(12 pts)*K-COLOR. Given a graph G = (V,E), a k-coloring is a function c: V -> {1, 2, … , k} such that c(u) ¹ c(v) for every edge (u,v) Î E. In other words the number 1, 2, .., k represent the k colors and adjacent vertices must have different color The decision problem K-COLOR asks if a graph can be colored with

at most K colors.

- a. The 2-COLOR decision problem is in P. Describe an efficient algorithm to determine if a graph has a 2-coloring. What is the running time of your algorithm?

- b. It is known that the 3-COLOR decision problem is NP-complete by using a reduction from SAT.

Use the fact that 3-COLOR is NP-complete to prove that 4-COLOR is NP-complete.