課程名稱︰資訊工程理論基礎
課程性質︰選修
課程教師︰呂育道
開課學院：電資學院
開課系所︰資工系
考試日期（年月日）︰2014.11.11
考試時限（分鐘）：180
是否需發放獎勵金：是
（如未明確表示，則不予發放）
試題 :
Theory of Computation
Mid-Term Exam, 2014 Fall Semester,
11/11/2014
Note: Unless stated otherwise, you may use any results proved in class
Problem 1 (25 points)
A Boolean function f:{0, 1}^m → {0, 1} is symmetric if f(x_1, x_2, ... , x_m)
depends only on Σ x_i. How many distinct symmetric Boolean functions of m
i
variables are there?
m+1
Ans: 2
Problem 2 (20 points)
Let A and B be two complexity classes. We say that the inclusion is proper if
A ⊂ B. Consider the following chain of class inclusions introduced in class:
L ⊆ NL ⊆ P ⊆ NP ⊆ PSPACE.
We can be sure that (at least) two pairs of classes have proper inclusions.
Which are they and why?
PS. let ⊂ means proper inclusions symbol http://i.imgur.com/qBeQO2V.png
Ans: L ⊂ PSPACE (see slide p. 234) and
NL ⊂ PSPACE (see homework 3 problem 1).
Problem 3 (25 points)
(a) Denote L(M) as the language L accepted by Turing machine M. Is the
language decidable? Why?
L = {(M) | M is a Turing machine and L(M) is countable}
(b) Does there exist a language which is not recursively enumerable? If your
answer is "NO", justify your answer; otherwise, give an example.
Ans:
(a) Yes, L is decidable. In fact, L is the language of all TM's, which
can be easily checked in polynomial time.
(b) Yes, there exist languages which are not recursively enumerable, for
example,
{(M, x) | M is a TM and it does not halt on string x}
Problem 4 (30 points)
Reduce k-SAT to 3SAT, where k > 3. (Hint: Consider the Boolean expressions
A, B, and C and the variable y. It is known that the expression
(y∪A) ∩ (﹁y∪B) ∩ C
is satisfiable if and only if
(A∪B) ∩ C
is too.)
Ans:
Consider a k-SAT expression Φ with n variables, m clauses and k literals in
every clause, where n > k. Let c_1, c_2, ... , c_m be the clauses of Φ. For
each c_j of the form
c_j = (w_1 ∪ w_2 ∪ ... ∪ w_(k-1) ∪ w_k), j = 1, 2, ... , m,
where w_1, w_2, ... , w_k are the literals, we introduce new variables
y_(j,1), y_(j,2), ... , y_(j,k-3) to form a new clause c'_j to replace c_j:
c'_j = (w_1 ∪ w_2 ∪ y_(j,1)) ∩ (﹁y_(j,1) ∪ w_3 ∪ y_(j,2))
∩ (﹁y_(j,2) ∪ w_4 ∪ y_(j,3))
∩ ...
∩ (﹁y_(j,k-4) ∪ w_(k-2) ∪ y_(j,k-3))
∩ (﹁y_(j,k-3) ∪ w_(k-1) ∪ w_k)
The above replacement is clearly a polynomial-time reduction.
Note that the results of the hint can be easily extended inductively such that
c'_j is satisfiable if and only if c_j is also satisfiable.
Now, we show that c'_1 ∩ c'_2 ∩ ... ∩ c'_m is satisfiable if Φ is. Suppose
Φ is satisfied by a truth assignment T. We extend T by assigning the values
of the new variables arbitrarily to form a new truth assignment T'. With the
extended results of the hint, c'_1 ∩ c'_2 ∩ ... ∩ c'_m must be satisfied by
T' because the new variables do not affect the result. Hence,
c'_1 ∩ c'_2 ∩ ... ∩ c'_m is satisfiable if Φ is.
Conversely, suppose c'_1 ∩ c'_2 ∩ ... ∩ c'_m is satisfied by a truth
assignment T'. Again, from the extended results of the hint, it is obvious
that Φ is also satisfied by T' by ignoring the values of all the new
variables y_(j,1), y_(j,2), ... , y_(j,k-3). Hence, Φ is satisfiable if
c'_1 ∩ c'_2 ∩ ... ∩ c'_m is.