SOLVED EECS 376 Homework 8

  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: 1 EECS 376: Foundations of Computer Science  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: 2 EECS 376: Foundations of Computer Science   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: 3