Description

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


If Y is NPcomplete then so is X.



If X is NPcomplete then so is Y.



If Y is NPcomplete and X is in NP then X is NPcomplete.



If X is NPcomplete and Y is in NP then Y is NPcomplete.



If X is in P, then Y is in P.



If Y is in P, then X is in P.


(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 wellknown NPcomplete problem SUBSETSUM: 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 SUBSETSUM is NPcomplete:


SUBSETSUM ≤p COMPOSITE.



If there is an O(n^{3}) algorithm for SUBSETSUM, then there is a polynomial time algorithm for

COMPOSITE.


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



If P NP, then no problem in NP can be solved in polynomial time.


(8 pts) A Hamiltonian path in a graph is a simple path that visits every vertex exactly once. Prove that HAMPATH = { (G, u, v ): there is a Hamiltonian path from u to v in G } is NPcomplete. You may use the fact that HAMCYCLE is NPcomplete.

(12 pts) KCOLOR. Given a graph G = (V,E), a kcoloring 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 colors. The decision problem KCOLOR asks if a graph can be colored with at most K colors.

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

It is known that the 3COLOR decision problem is NPcomplete by using a reduction from SAT. Use the fact that 3COLOR is NPcomplete to prove that 4COLOR is NPcomplete.