Description
1. (a) Prove the transitive property for polynomial-time mapping reductions:
A ≤p B and B ≤p C =⇒ A ≤p C.
(b) Prove that if A ≤p B and B ∈ NP, then A ∈ NP.
(c) Prove that if A ≤p B, then A ≤T B.
Solution:
2. Recall the 0-1 Knapsack Problem: we are given two length-n arrays containing positive integer
weights W = (w1, w2, . . . , wn) and values V = (v1, v2, . . . , vn), and a weight capacity C ∈ N.
The goal is to select items having maximum total value whose total weight is below the
threshold. We can define this as a decision problem by introducing a threshold K and asking
whether a value of at least K can be achieved (subject to the weight constraint):
Knapsack = {(W, V, C, K) : ∃ S ⊆ {1, . . . , n} such that X
i∈S
W[i] ≤ C and X
i∈S
V [i] ≥ K}.
In this problem you will show that Knapsack is NP-Complete.
(a) Prove that Knapsack ∈ NP.
(b) Prove that Knapsack is NP-Hard, by showing that Subset-Sum ≤p Knapsack.
Conclude that Knapsack is NP-Complete.
(c) Recall that we previously gave a dynamic programming algorithm that solves Knapsack
in O(nC) time. Does this prove that P = NP? Why or why not?
Solution:
3. Recall that Clique ∈ NP, where Clique is defined as:
Clique = {hG, ki : G = (V, E) has a clique of size ≥ k}.
(Recall: A clique of an undirected graph G = (V, E) is a subset K ⊆ V such that every pair
of vertices in K has an edge between them.) Consider the following variant of Clique:
Half-Clique = {hGi : |V | = 2n, and G has a clique of size ≥ n}.
Prove that Half-Clique is NP-complete.
Solution:
4. Suppose there are n students at Michigan and k clubs. Every student may join any number
of clubs, possibly zero. Let S = (S1, . . . , Sk) be a list of the students in each club, where each
club i has a subset Si ⊂ [n] of students.
Now given a tuple q = (q1, . . . , qk) of natural numbers, we want to enroll a subset of Michigan
students in EECS 376 so that there are exactly qi EECS 376 students in the ith club, for
every i ∈ [k].
We say q is a possible configuration if this is possible. Note that not all qs are possible
configurations. For example, if Si = [n] for every i ∈ [k], i.e. every student joins every club,
then the only possible q’s are (w, w, . . . , w) for some w ∈ {0, 1, . . . , n} where w is the number
of EECS 376 students.
Concretely, define
Poss-Config = {hn, k, S, qi : q is a possible configuration, i.e. there exists E ⊂ [n],
representing the set of EECS 376 students, such that
for every i ∈ [k], |Si ∩ E| = qi}.
Prove that 3SAT ≤p Poss-Config.
Hints:
(a) For each variable vi
in ϕ, allocate two students to represent when vi = T and vi = F,
respectively. How can you enforce that exactly one of them is enrolled in EECS 376
(perhaps by definition of a corresponding club)?
(b) Assuming you’ve dealt with hint (a), how do you capture the constraint that all clauses
evaluate to true (again by definition of a corresponding club)?
Solution:
5. Let EXP be the class of all languages which are decidable in exponential time, i.e., in time
O(2n
k
) for some constant k (where n is the length of input). Formally,
EXP =
[
k∈N
DTIME
2
n
k
.
It remains unknown whether NP = EXP, but it is known that P 6= EXP. Prove that NP ⊆ EXP.
That is, for any language L ∈ NP and any input x ∈ L, provide a decider that runs in time
O(2n
k
), where n = |x| and k is some constant. Recall that any language L ∈ NP has a
verifier V (x, c) which runs in time O(|x|
d
) for a constant d. (As always, you should analyze
the correctness and runtime of your decider.)
Solution:
