课程名称︰资讯工程理论基础 课程性质︰选修 课程教师：吕育道 开课学院：电资学院 开课系所︰资工所 考试日期（年月日）︰2016.01.12 考试时限（分钟）： 试题 : Theory of Computation Final Exam, 2015 Fall Semester, 1/12/2016 Note: Unless stated otherwise, you may use any results proved in class. Problem 1 (25 points) Reduce 3SAT to INTEGER PROGRAMMING. Ans: Let the variables in the 3SAT formula be x_1, x_2, …, x_n. We will have corresponding variables z_1, z_2, …, z_n in our integer program. First, we restrict each variable z_i such that 0 ≦ z_i ≦ 1, for all i. Assigning z_i = 1 in the integer program represents setting x_i = true in the 3SAT formula, and assigning z_i = 0 represents setting x_i = false. For each clause such as (x_1 Ｖ ﹁x_2 Ｖ x_3), we can rewrite it as the integer program: z_1 + (1 - z_2) + z3 > 0. To satisfy this inequality, we must either set z_1 = 1 or z_2 = 0 or z_3 = 1, which means we either set x_1 = true or x_2 = false or x_3 = true in the corresponding truth assignment. Assigning true/false to every x_i in all clauses, we then will have a set of input of integer programming that is equivalent to the given set of input to 3SAT. Problem 2 (25 points) For the Diffie-Hellman Secret-Key Agreement Protocol, Alice and Bob agree on a large prime p and a primivite root g of p (where p and g are public). Alice chooses a random a and Bob also chooses a random b. 1. (10 points) What are the values of α, β and the common key? 2. (15 points) For p = 11, g = 2, a = 4 and b = 5, what are the values of α, β and the common key? Ans: 1. The values of α and β are α ≡ g^a (mod p), β ≡ g^b (mod p), and the common key is α^b ≡ g^(ab) ≡ g^(ba) ≡ β^a (mod p). 2. For p = 11, g = 2, a = 4 and b = 5, the values of α and β are α ≡ 2^4 ≡ 5 (mod 11), β ≡ 2^5 ≡ 10 (mod 11), and the common key is α^b ≡ 2^(4*5) ≡ β^a ≡ 1 (mod 11). Problem 3 (25 points) Prove that NP ⊆ ZPP, then NP ⊆ BPP. Ans: Assume NP ⊆ ZPP. Pick any NP-complete language L. We only need to show that L ∈ BPP. There exists an algorithm A that decides L in expected polynomial time, say p(n). By Markov's inequality, the probability that the running time of A exceeds 3p(n) is at most 1/3. Run A for 3p(n) steps to determine with probability at least 1 - 1/3 = 2/3 whether the input belongs in L. We therefore obtain a polynomial-time algorithm for L which errs with probability at most 1/3 on each input. Hence L is in BPP. Problem 4 (25 points) Let G = (V, E) be an undirected graph in which every node has a degree of at most k. Let I be a nonempty set. I is said to be independent if there is no edge between any two nodes in I. k-DEGREE INDEPENDENT SET asks if there is an independent set of size k. Consider the following algorithm for k-DEGREE INDEPENDENT SET: 1: I := ψ; 2: while ∃v ∈ G do 3: Add v to I; 4: Delete v and all of its adjacent nodes from G; 5: end while; 6: return I; Show that this algorithm for k-DEGREE INDEPENDENT SET is a k/(k+1)-approximation algorithm. Recall that an ε-approximation algorithm returns a solution that is at least (1 - ε) times the optimum for maximization problems. Ans: Since each stage of the algorithm adds a node to I and deletes at most k + 1 nodes from G, I has at least |V|/(k+1) nodes, which is at least 1/(k+1) times the size of the optimum independent set because the size of the optimum independent set is trivially at most |V|. Thus this algorithm returns solutions that are never smaller than 1 - 1/(k+1) = k/(k+1) times the optimum. Problem 5 (25 points) A cut in an undirected graph G = (V, E) is a partition of the nodes into two nonempty sets S and V - S. MAX BISECTION asks if there is a cut of size at least K such that |S| = |V - S|. It is known that MAX BISECTION is NP-complete. BISECTION WIDTH asks if there is a bisection of size at most K such that |S| = |V - S|. Show that BISECTION WIDTH is NP-complete. You do not need to show it is in NP. Ans: See pp. 392-393 in the slides. Problem 6 (25 points) Is x^4 ≡ 25 mod 1013 solvable and why? Ans: Let's first notice that 1013 is a prime. Since 25 has square roots ±5, we need to check if any of the Legendre symbols (5/1013) or (-5/1013) is 1. We have ╭ 5 ╮ ╭ 1013 ╮ ╭ 3 ╮ │───│ = │───│ = │──│ = -1 ╰ 1013 ╯ ╰ 5 ╯ ╰ 5 ╯ and ╭ -5 ╮ ╭ -1 ╮╭ 5 ╮ │───│ = │───││───│ ╰ 1013 ╯ ╰ 1013 ╯╰ 1013 ╯ (1013-1)/2╭ 5 ╮ ╭ 5 ╮ = (-1) │───│ = │───│ = -1 ╰ 1013 ╯ ╰ 1013 ╯ so 25 is not a quadratic residue modulo 1013 and cannot be a solution to x^4 ≡ 25 mod 1013. Problem 7 (25 points) Let n ∈ Z+ with n ≧ 2. Let ψ(n) stand for Euler's totient function, which counts the number of positive integers smaller than n and are relative prime to n. 1. (5 points) Determine ψ(2^n). 2. (10 points) Determine ψ(ψ(2^n)). 3. (10 points) Determine ψ((2p)^n) where p is an odd prime. Ans: 1. ψ(2^n) = 2^n - 2^(n-1) = 2^(n-1) (2-1) = 2^(n-1). 2. ψ(ψ(2^n)) = ψ(2^(n-1)) = 2^(n-1) - 2^(n-2) = 2^(n-2) (2-1) = 2^(n-2). 3. ψ((2p)^n) = ψ((2^n)(p^n)) = ψ(2^n) ψ(p^n) = 2^(n-1) (p^n - p^(n-1)) = 2^(n-1) p^(n-1) (p-1). --

※ 发信站: 批踢踢实业坊(ptt.cc), 来自: 1.163.254.247 ※ 文章网址: https://webptt.com/cn.aspx?n=bbs/NTU-Exam/M.1461481894.A.CFB.html ※ 编辑: rod24574575 (1.163.254.247), 04/24/2016 15:11:58