Problem 1: (7 points)
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? Explain.
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-complete.
D) If X is NP-complete and Y is in NP then Y is in NP-complete.
E) X and Y can’t both be NP-complete.
F) If X is in P, then Y is in P. G) If Y is in P, then X is in P.
Problem 2: (4 points)
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 the 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 for COMPOSITE.
C) If there is a polynomial algorithm for COMPOSITE, then P = NP.
D) If P != NP, then no problem in NP can be solved in polynomial time.
Problem 3: (3 points)
Two well-known NP-complete problems are 3-SAT and TSP, the traveling salesman problem. The 2-SAT problem is a SAT variant in which each clause contains at most two literals. 2-SAT is known to have a polynomial-time algorithm. Is each of the following statements true or false? Justify your answer.
A) 3-SAT <=p TSP
B) If P != NP, then 3-SAT <=p 2-SAT
C) If P != NP, then no NP-complete problem can be solved in polynomial time.
Problem 4: (6 points)
A Hamiltonian path in a graph is a simple path that visits every vertex exactly once. Show 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.
Problem 5: (5 points)
LONG-PATH is the problem of, given (G,u,v,k) were G is a graph, u and v vertices and k an integer, determine if there is a simple path in G from u to v of length at least k. Prove that LONG-PATH in NP-complete.
