→ rod24574575 : 已收資訊系精華區! 01/15 12:03
課程名稱︰資訊工程理論基礎
課程性質︰選修
課程教師：呂育道
開課學院：電資學院
開課系所︰資工所
考試日期（年月日）︰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://www.ptt.cc/bbs/NTU-Exam/M.1484452912.A.39B.html