SOLVED EECS 376 Homework 7

  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  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   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