课程名称︰资讯工程理论基础 课程性质︰选修 课程教师：吕育道 开课学院：电资学院 开课系所︰资工所 考试日期（年月日）︰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/cn.aspx?n=bbs/NTU-Exam/M.1461475151.A.F7F.html