EECS 376: Foundations of Computer Science Homework 7

EECS 376: Foundations of Computer Science Homework 7 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. In this question we examine the validity of verifiers and deciders for showing membership in NP or P. (a) Recall LACC = {(hMi, x) : M is a TM that accepts x} Is the program V a verifier for LACC, where the certificate C ≥ 1 is an integer represented in binary? (Hint: Is V efficient?) Show why or why not. V = “On input (hMi, x, C): 1. Run M on x for C steps 2. If M accepts x in those C steps, ACCEPT. Else, REJECT.” Solution: (b) Define First-Digit-Factorial = {n ∈ N : the first digit of the decimal representation of n! is 2}, where the first digit is the most significant digit. Does F show that First-Digit-Factorial ∈ P? Show why or why not. F = “On input n: 1. product ← 1 2. For i from 2 to n 3. product ← product · i 4. digit ← product 5. While digit ≥ 10 6. digit ← bdigit/10c 7. If digit = 2, ACCEPT. Else REJECT.” Solution: 1 EECS 376: Foundations of Computer Science University of Michigan, Fall 2023 Homework 7 Due 8:00pm, Nov 1 (accepted until 9:59 pm, no credit after) 2. Show that the following languages are in the class NP. Note: To prove that a language is in NP, you must provide a verifier and prove that your verifier satisfies correctness and efficiency. (a) Ham-Cycle = {hGi : G is an undirected graph with a Hamiltonian cycle}. Note: a Hamiltonian cycle for a graph is a path that visits each node exactly once and ends at the starting node. Solution: (b) For two graphs G = (V, E), G0 = (V 0 , E0 ), an isomorphism between them is a bijection γ : V → V 0 such that (a, b) ∈ E if and only if (γ(a), γ(b)) ∈ E0 . Similarly, G and G0 are said to be isomorphic if there exists an isomorphism between them. For example, the following two graphs are isomorphic, by the bijection γ where γ(1) = 1, γ(2) = 3, γ(3) = 5, γ(4) = 2, γ(5) = 4. 1 2 3 4 5 1 2 3 4 5 Define Graph-Isomorphism = {(hGi,hHi) : G, H are isomorphic graphs}. Solution: (c) Define Not-Prime = {n ∈ N : n is not a prime number} Solution: 3. (a) Let A, B be two languages in P. Then show the language A ∪ B is also in P. Solution: (b) Let A, B be two languages in NP. Then show the language A ∪ B is also in NP. Solution: (c) Let A, B ∈ P. Define AB = {ab : a ∈ A, b ∈ B} where ab denotes the concatenation of a and b. For example, if a = 100111 and b = 0011 are bitstrings then ab = 1001110011. Show that AB ∈ P. 2 EECS 376: Foundations of Computer Science University of Michigan, Fall 2023 Homework 7 Due 8:00pm, Nov 1 (accepted until 9:59 pm, no credit after) Solution: 4. This question explores the complexity class coNP =  L   L ∈ NP . Conceptually, NP contains the languages whose “yes” instances can be verified efficiently, whereas coNP contains the languages whose “no” instances can be verified efficiently. (a) Prove that P is closed under set complement. That is, for any L ∈ P, we have L ∈ P. Solution: (b) Use part (a) to prove that if P = NP, the following set inclusions hold: (i) NP ⊆ coNP (that is, for any L ∈ NP, we have L ∈ coNP), and (ii) coNP ⊆ NP. Solution: (c) Conclude from part (b) that if NP 6= coNP, then P 6= NP. Solution: 3