50.004-Homework Set 6 Solved

Question 1. For each of the following statements, determine if it is true, false, or a statement that we are still not sure yet whether it is true or false. You do not have to justify your answers.

 

(i)        All NP-complete problems are solvable in polynomial time.

(ii)      All NP-hard problems are solvable in polynomial time.

(iii)    An NP-complete problem must be solvable in exponential time.

(iv)    An undecidable problem today is a problem that could potentially be solved in the future, with sufficient computational resources.

(v)      A problem in class NP is by definition only solvable using non-deterministic algorithms.

Question 2. We have covered several NP-complete problems in Weeks 12, and we will cover more NP-complete problems in Week 13. For this question, please give two other NP-complete problems not mentioned in class (Weeks 12–13). One of your NP-complete problems should be a graph-related problem; and the other should be a non-graph-related problem.

To get full credit for each NP-complete problem, you would have to specify exactly what the problem is (not just the name of the problem), and you would have to indicate very clearly what the input(s) to the problem is/are, and what the output(s) to the problem is/are. In particular, is the output a “yes/no” answer, a numerical answer (e.g. the minimum number satisfying a certain condition), or something else (e.g. a path in a graph)? Is the input a set of objects, or a sequence of numbers, or something else? If your input is a graph, is this graph directed or undirected? Weighted or unweighted? Simple, or non-simple? Also, if your NP-complete problems involve any terminology, notation, or concepts, not covered in this course, you would have to define them.             

Question 3. During Week 12’s cohort class, we introduced the “Hamiltonian path problem”, which has as its input a simple undirected graph, and which has as its output a “yes/no” answer, on whether the input graph contains a Hamiltonian path. Now consider a slight variant of the problem, called the “directed Hamiltonian path problem”, which has as its input a simple directed graph, and which has as its output a “yes/no” answer, on whether the input graph contains a Hamiltonian directed path.

Show that there is a polynomial-time reduction of this “directed Hamiltonian path problem” to the (undirected) “Hamiltonian path problem”.

Question 4. Show that there is a polynomial-time reduction of the (undirected) “Hamiltonian path problem” to the “directed Hamiltonian path problem”.

Warning: No credit will be given if your answers to Questions 3 and 4 are switched, i.e. your answer to Question 3 is actually a correct solution to Question 4, and your answer to Question 4 is actually a correct solution to Question 3.

1

Remark: Recall that a (directed or undirected) graph is called simple if it has no loops and no multiple edges. Remember, a graph is said to have no multiple edges if for every two distinct vertices, there is at most one edge incident to both vertices. In particular, if G is a simple directed graph, and if u and v are distinct vertices of G, then at most one of the two ordered pairs (u,v) and (v,u) can be a directed edge of G.

Question 5. The subset-sum decision problem is a decision problem stated as follows: Given a finite set T of positive integers and a positive integer k, decide (i.e. yes or no) whether there exists a subset T0 ⊆ T whose elements sum up to k.

Show that there is a polynomial-time reduction of the subset-sum decision problem to the partition problem (as stated in L12.01).