课程名称︰资讯工程理论基础 课程性质︰选修 课程教师：吕育道 开课学院：电资学院 开课系所︰资工所 考试日期（年月日）︰2017.01.10 考试时限（分钟）： 试题 : Theory of Computation Final Exam, 2016 Fall Semester, 1/10/2017 Note: Unless stated otherwise, you may use any results proved in class Problem 1 (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. For p = 23, g = 5, a = 6 and b = 15, what are the values of α, β and the common key? Ans: For p = 23, g = 5, a = 6 and b = 15, the values of α and β are α ≡ 5^6 ≡ 8 (mod 23), β ≡ 5^15 ≡ 19 (mod 23), and the common key is a^b ≡ 8^15 ≡ β^α ≡ 2 (mod 23). Problem 2 (25 points) Prove that if every language in BPP only needs a pseudorandom generator which stretches a random seed of logarithmic length, then BPP = P. Ans: We only need to show BPP ⊆ P. Run the BPP algorithm for each of the seeds. There are only 2^(O(log n)) = O(n^c) seeds, a polynomial Accept if and only if at least 3/4 of the outcomes is a "yes". The running time is deterministically polynomial. Problem 3 (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 relatively 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) Problem 4 (25 points) Prove that there is no ε-approximation algorithm for the NP-complete 6-COLORING if ε < 1/7 and assuming P ≠ NP. Recall that an ε-approximation algorithm F guarantees that OPT OPT ≦ c(F(G)) ≦ ─── 1 - ε where c(F(G)) is the number of colors the polynomial-time algorithm F uses to color G. Ans: We prove the problem by contradiction. We assume that there exists an ε-approximation algorithm F that colors the graph G in polynomial time. Given ε < 1/7, F will color G with at most OPT x = ─── = 6 1 - ε in polynomial time if G is 6-colorable. That is, F can answer YES or NO to the NP-complete problem 6-COLORING in polynomial time. --

※ 发信站: 批踢踢实业坊(ptt.cc), 来自: 59.115.46.186 ※ 文章网址: https://webptt.com/cn.aspx?n=bbs/NTU-Exam/M.1484452912.A.39B.html