课程名称︰资讯工程理论基础
课程性质︰选修
课程教师：吕育道
开课学院：电资学院
开课系所︰资工所
考试日期（年月日）︰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.