课程名称︰资讯工程理论基础 课程性质︰选修 课程教师：吕育道 开课学院：电资学院 开课系所︰资工所 考试日期（年月日）︰2016.10.25 考试时限（分钟）： 试题 : Theory of Computation Midterm Examination on October 25, 2016 Fall Semester, 2016 Problem 1 (25 points) Prove that the following language L is undecidable: L = {M; x; n│a TM M with input x executes the nth instruction of M.} Ans: Suppose that L is decidable. We now reduce the halting problem to L. Consider an instance M; x. Then replace all instructions δ(q, s) = (r, t, D), where r is a "yes", a "no", or an h, with δ(q, s) = (Q, t, D), where Q is a new state. Then add instructions which make the head move to the beginning of the tape (with symbol▕╳) while remaining at state Q. Let k be the number of instructions of the aforesaid machine. Finally, add the instruction δ(Q,▕╳) = (h,▕╳, —) numbered n = k + 1. Call this modified machine M'. Now we construct a TM M" such that ╭ "yes", if M'(x) executes the nth instruction; M"(M'; x; n) = < ╰ "no", otherwise. Clearly M'; x; n ∈ L if and only if M; x ∈ H, a contradiction. Hence L is undecidable. Problem 2 (25 points) _ Prove that if L is recursively enumerable but not recursive, then L is not recursively enumerable. _ _ Ans: Assume that L is recursively enumerable. Then both L and L are recursively enumerable (see p. 150 of the slides). This implies that L is recursive, a contradiction. Problem 3 (25 points) 1. Show that the satisfiability of DNF is polynomial-time solvable. 2. By transforming any boolean expression into a DNF (as explained in the slides), we can solve all satisfiability problem in polynomial time. What is wrong with this argument. Ans: 1. A DNF is satisfiable if and only if there is at least one implicant which does not contain some variable and its negation. Testing this condition is easy. So, the satisfiability of DNF is polynomial-time solvable. 2. The reduction may take exponential time. Problem 4 (25 points) Let L be an NP-complete language. Prove that P = NP if and only if L ∈ P. Ans: First, suppose L ∈ P. Every language L' ∈ NP can reduce to L because L is an NP-complete language. Since P is closed under reductions, L' ∈ P. Thus NP ⊆ P. As P ⊆ NP, we conclude that P = NP. On the other hand, suppose P = NP. As L ∈ NP, it is obvious that L ∈ P. --

※ 发信站: 批踢踢实业坊(ptt.cc), 来自: 61.228.166.1 ※ 文章网址: https://webptt.com/cn.aspx?n=bbs/NTU-Exam/M.1480731691.A.749.html