課程名稱︰資訊工程理論基礎 課程性質︰必修 課程教師︰呂育道 開課學院：電資學院 開課系所︰資工系 考試日期（年月日）︰2013.11.05 考試時限（分鐘）：180 是否需發放獎勵金：是 （如未明確表示，則不予發放） 試題 : Theory of Computation Mid-Term Examination on November 5, 2013 Fall Semester, 2013 Problem 1 (25 points) Show that if NP ≠ coNP, then P ≠ NP. Ans: P is closed under complementation. If P = NP, then NP is also closed under complementation. In other words, NP = coNP. Problem 2 (25 points) It is known that H* = {M | M halts on all inputs} is undecidable. Show that L is undecidable, where L = {M_1;M_2 | M_1 and M_2 are TMs and M_1(x) = M_2(x) for all inputs x}. Ans: We prove that L is undecidable by reducing H* to L. Suppose L is decidable. Given a TM M, we construct M_1 and M_2 as follows. M_1 simulates M on any input and accepts if M halts. M_2 always accepts on its input. Obviously, M halts on all inputs if and only if M_1(x) = M_2(x) for all inputs x. So M ∈ H* if and only if M_1;M_2 ∈ L. So if L were decidable, H* would be decidable, a contradiction. Hence, L is undecidable. Problem 3 (25 points) Prove that the language C_NP is NP-complete, where C_NP = {(N, x, 0^t) | N is an NTM that accepts x within time t}. Recall that 0^k denotes the string consisting of k 0s. Do not forget to show C_NP is in NP. Ans: We first show that C_NP is in NP. With the input (N, x, 0^t), we simulate N on x up to t steps of N and accept if N accepts x. The algorithm obviously runs in polynomial time. We next show that C_NP is NP-hard. Let L ∈ NP be accepted by an NTM N that runs in polynomial time n^c for some constant c. To reduce L to C_NP, simply map the input x to the triple (N, x, 0^(n^c)). The reduction can evidently be performed in polynomial time. It is clear that x ∈ L iff (N, x, 0^(n^c)) ∈ C_NP. Problem 4 (25 points) We say that a function f: Z^(+) → Z^(+) is a proper complexity function if 1. f is non-decreasing, i.e, f(n+1) ≧ f(n) for all positive integers n. 2. There is a k-string Turing Machine M_f with input and output that, given an input of length n, (a) outputs ㄇ^f(n) on its output string in time O(n + f(n)), and (b) uses O(f(n)) space besides its input and output. PS. ㄇ = output symbol Show that the set of proper complexity functions is closed under sums (i.e., if f and g are proper complexity functions, then f + g is also a proper complexity function.) Ans: Let f and g be two proper complexity functions. Let's notice that 1. For all positive integers n, (f+g)(n + 1) = f(n + 1) + g(n + 1) ≧ f(n) + g(n) = (f+g)(n) because f and g are non-decreasing; hence (f+g) is also non-decreasing. 2. Let M_f and M_g be the (k_f)-string and (k_g)-string Turing machines associated with f and g, respectively. Let's construct a (k_f + k_g)-string Turing machine called M_(f+g) as follows: (a) Given an input of length n, M_(f+g) first emulates M_f on it to write ㄇ^f(n) in the (k_f)th string. (b) Then M_(f+g) emulates M_g on the original input to write ㄇ^g(n) in the (k_f + k_g - 1)st string. (c) Finally, M_(f+g) concatenates the (k_f)th and (k_f + k_g - 1)st strings and outputs it in the (k_f + k_g)th tape. From the construction above, we notice that given an input of length n, the output of M_(f+g) is of length (f+g)(n) = f(n) + g(n). Now, let's notice that (a) M_(f+g) runs in time O(n + f(n) + n + g(n) + f(n) + g(n)) = O(n + f(n) + g(n)). (b) The maximum space M_(f+g) uses is O(f(n)) + O(g(n)) = O(f(n) + g(n)). From the two items above, (f+g) is a proper complexity function, hence the set of all proper complexity functions is closed under sums. --

※ 發信站: 批踢踢實業坊(ptt.cc), 來自: 1.160.217.112 ※ 文章網址: http://webptt.com/m.aspx?n=bbs/NTU-Exam/M.1416382078.A.F49.html ※ 編輯: rod24574575 (1.160.217.112), 11/19/2014 16:38:59