EECS 376: Foundations of Computer Science Homework 8

EECS 376: Foundations of Computer Science

Homework 8 We may grade a subset of the assigned questions, to be determined after the deadline, so that we can provide better feedback on the graded questions. Unless otherwise stated, each question requires sufficient justification to convince the reader of the correctness of your answer. For bonus questions, we will not provide any insight during office hours or Piazza, and we do not guarantee anything about the difficulty of these questions. We strongly encourage you to typeset your solutions in LATEX. If you collaborated with someone, you must state their name(s). You must write your own solution for all problems and may not look at any other student’s write-up. 0. If applicable, state the name(s) and uniqname(s) of your collaborator(s). Solution: 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 University of Michigan, Fall 2023 Homework 8 Due 8:00pm, Nov 8 (accepted until 9:59 pm, no credit after) 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 University of Michigan, Fall 2023 Homework 8 Due 8:00pm, Nov 8 (accepted until 9:59 pm, no credit after) 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