課程名稱︰資訊工程理論基礎 課程性質︰選修 課程教師︰呂育道 開課學院：電資學院 開課系所︰資工系 考試日期（年月日）︰2014.12.16 考試時限（分鐘）：180 試題 : Theory of Computation Midterm Examination on December 16, 2014 Fall Semester, 2014 Problem 1 (25 points) Let G(V, E) be a directed graph with vertices V and edges E, and |V| be the number of vertices in G. HAMILTONIAN CYCLE asks if there is a cycle through a graph G which visits each vertex exactly once. It is known that HAMILTONIAN CYCLE is NP-complete. BIGCYCLE asks if G has a cycle of length equal or larger than |V|/2. Reduce HAMILTONIAN CYCLE to BIGCYCLE. Ans: Let N be an NTM which decides BIGCYCLE. Construct an NTM M which decides HAMILTONIAN CYCLE as follows: 1: On input G(V, E) with |V|. 2: Add exactly |V| isolated vertices to G to obtain G'. 3: Run N(G'). 4: If N accepts, halt and accept. 5: Otherwise, halt and reject. Clearly G ∈ HAMILTONIAN CYCLE if and only if G' ∈ BIGCYCLE. M clearly runs in polynomial time. It completes the proof. Problem 2 (25 points) Let a, b, n, m be any odd integers. Show that if gcd(ab, nm) = 1, then (ab^2 | nm^2) = (a | n). (Recall that (ab | m) = (a | m)(b | m) when gcd(ab, m) = 1 and (a | nm) = (a | n)(a | m) when gcd(a, nm) = 1.) Ans: (ab^2 | nm^2) = (a | nm^2)(b^2 | nm^2) = (a | n)(a | m^2)(b | nm^2)(b | nm^2) = (a | n)(a | m)(a | m)(b | nm^2)^2 = (a | n)(a | m)^2 = (a | n) Problem 3 (25 points) Show that if 3-SAT has uniform polynomial circuits, then NP = coNP. Ans: By Theorem 74 (see p.613 in the slides), 3-SAT is then in P. As 3-SAT is NP-complete, by Corollary 29 (see p.292 in the slides) P = NP = coNP. Problem 4 (25 points) Show that RP is closed under union. (This means that L_1∪L_2 ∈ RP if L_1 ∈ RP and L_2 ∈ RP. Recall that the error probability does not have to be exactly 1/2; any constant will do.) Ans: Let L_1 and L_2 ∈ RP be decided by polynomial-time Monte Carlo TMs N_1 and N_2, respectively. Note that for i = 1, 2, and ε_i = 1/2, Pr(N_i(x) = 1 | x ∈ L_i) ≧ 1 - ε_i and Pr(N_i(x) = 1 | x !∈ L_i) = 0. To show that RP is closed under union, let TM N_∪ simulate N_1 and N_2 with independent coin flips on input x. N_∪(x) = 1 if N_1 or N_2 accepts x; otherwise, N_∪(x) = 0. Now we prove that N_∪ decides L_1∪L_2 with one-sided error probability ε = ε_1 ε_2. Note that 0 ＜ ε ≦ 1. Assume x ∈ L_1∪L_2. Then Pr(N_∪(x) = 1) ＝ 1 - Pr(N_∪(x) = 0) ＝ 1 - Pr(N_1(x) = 0) × Pr(N_2(x) = 0) ≧ 1 - ε_1 ε_2 ＝ 1 - ε Hence ε = 1/4. Now assume x !∈ L_1∪L_2. This implies that Pr(N_1(x) = 1) = Pr(N_2(x) = 1) = 0. So, Pr(N_∪(x) = 1) ＝ 1 - Pr(N_∪(x) = 0) ＝ 1 - Pr(N_1(x) = 0) × Pr(N_2(x) = 0) ＝ 1 - (1 - Pr(N_1(x) = 1)) × (1 - Pr(N_2(x) = 1)) ＝ 0 Clearly, L_1∪L_2 ∈ RP, and the claim holds. --

※ 發信站: 批踢踢實業坊(ptt.cc), 來自: 111.250.50.176 ※ 文章網址: http://webptt.com/m.aspx?n=bbs/NTU-Exam/M.1419032759.A.99D.html