課程名稱︰資訊工程理論基礎 課程性質︰選修 課程教師：呂育道 開課學院：電資學院 開課系所︰資工所 考試日期（年月日）︰2015.11.10 考試時限（分鐘）： 試題 : Theory of Computation Midterm Examination on November 10, 2015 Fall Semester, 2015 Problem 1 (20 points) Prove that the halting problem H is complete for RE (the set of recursively enumerable languages). (Recall that a problem A is complete for RE if every language in RE can be reduced to A.) Ans: Let L be any recursively enumerable language. Assume M accepts L. Clearly, one can decide whether x ∈ L by asking if M: x ∈ H. This reduction is clearly computable. Hence all recursively enumerable languages are reducible to H! Problem 2 (20 points) Let P(x, y) be a binary predicate, and let Q be the unary predicate defined by Q(a) <=> ﹁P(a, a). Show that Q is distinct from all the predicates P_b, defined by P_b(a) <=> P(a, b). Ans: If Q is P_b, then P(b, b) <=> P_b(b) <=> Q(b) <=> ﹁P(b, b). Problem 3 (20 points) If the following language L is decidable, please give an algorithm; otherwise, prove that it is undecidable by reduction: L = {M│ M is a Turing machine and there exists an input whose length is less than |M| on which M halts}. Ans: L is undecidable. We reduce the halting problem H to L. Given an instance M;x, we construct the following TM M' with an arbitrary input y: ╭ yes, if M(x) ≠ ↗, M'(y) = ┤ ╰ ↗, otherwise. For any input y, M' halts at "yes" if and only if M halts on x. In other words, M' halts for all inputs including those of length less than |M'| if and only if M halts on x. So M' ∈ L if and only if M;x ∈ H. Hence, L is undecidable. Problem 4 (20 points) 1. (10 points) Give the definitions of (a) The complement of a complexity class. (b) Being closed under complements. 2. (10 points) Show that if NP ≠ coNP, then P ≠ NP. (Half of the grade will be deducted if any of (a) and (b) above is wrongly answered.) Ans: 1. For the definitions: (a) For any complexity class C, coC is defined as _ coC = {L: L ∈ C} (b) We say that a complexity class C is closed under complement if C = coC. 2. P is closed under complementation. If P = NP, then NP is also closed under complementation. In other words, NP = coNP. Problem 5 (20 points) Recall that NL = NSPACE(log n) and REACHABILITY ∈ NL. Prove that REACHABILITY is NL-complete. Ans: Let L ∈ NL be decided by a log-space NTM M. We proceed to prove that REACHABILITY is NL-hard by reducing L to REACHABILITY. Given input x, construct the polynomial-sized con guration graph G of M on input x (see p. 243 of the slides). Note that the nodes represent all configurations of M(x) and the edges represent legal transitions between configurations. Particularly, the START node and the ACCEPT node denote the starting configuration and the accepting configuration, respectively. G is represented by the adjacency matrix which can be generated by the following procedure: 1: for each configuration i do 2: for each configuration j do 3: if there is a legal transition between i and j then 4: Output 1; 5: else 6: Output 0; 7: end if 8: end for 9: end for 10: Output START, ACCEPT; The reduction can be done in O(log) space because i and j are encoded in binary. Clearly, x ∈ L if and only if R(x) ∈ REACHABILITY. So REACHABILITY is NL-complete. --

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