課程名稱︰資訊工程理論基礎
課程性質︰選修
課程教師：呂育道
開課學院：電資學院
開課系所︰資工所
考試日期（年月日）︰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.