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