Description
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.
[5 points]
(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. [5 points]
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”. [5 points]
Question 4. Show that there is a polynomial-time reduction of the (undirected) “Hamiltonian
path problem” to the “directed Hamiltonian path problem”. [5 points]
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 T
0 ⊆ 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). [5 points]
2
