课程名称︰资讯工程理论基础
课程性质︰必修
课程教师︰吕育道
开课学院：电资学院
开课系所︰资工系
考试日期（年月日）︰2013.11.05
考试时限（分钟）：180
是否需发放奖励金：是
（如未明确表示，则不予发放）
试题 :
Theory of Computation
Mid-Term Examination on November 5, 2013
Fall Semester, 2013
Problem 1 (25 points)
Show that if NP ≠ coNP, then P ≠ NP.
Ans: P is closed under complementation. If P = NP, then NP is also closed
under complementation. In other words, NP = coNP.
Problem 2 (25 points)
It is known that H* = {M | M halts on all inputs} is undecidable. Show that
L is undecidable, where
L = {M_1;M_2 | M_1 and M_2 are TMs and M_1(x) = M_2(x) for all inputs x}.
Ans: We prove that L is undecidable by reducing H* to L. Suppose L is
decidable. Given a TM M, we construct M_1 and M_2 as follows. M_1
simulates M on any input and accepts if M halts. M_2 always accepts on
its input. Obviously, M halts on all inputs if and only if M_1(x) = M_2(x)
for all inputs x. So M ∈ H* if and only if M_1;M_2 ∈ L. So if L were
decidable, H* would be decidable, a contradiction. Hence, L is
undecidable.
Problem 3 (25 points)
Prove that the language C_NP is NP-complete, where
C_NP = {(N, x, 0^t) | N is an NTM that accepts x within time t}.
Recall that 0^k denotes the string consisting of k 0s. Do not forget to show
C_NP is in NP.
Ans: We first show that C_NP is in NP. With the input (N, x, 0^t), we simulate
N on x up to t steps of N and accept if N accepts x. The algorithm
obviously runs in polynomial time. We next show that C_NP is NP-hard. Let
L ∈ NP be accepted by an NTM N that runs in polynomial time n^c for some
constant c. To reduce L to C_NP, simply map the input x to the triple
(N, x, 0^(n^c)). The reduction can evidently be performed in polynomial
time. It is clear that x ∈ L iff (N, x, 0^(n^c)) ∈ C_NP.
Problem 4 (25 points)
We say that a function f: Z^(+) → Z^(+) is a proper complexity function if
1. f is non-decreasing, i.e, f(n+1) ≧ f(n) for all positive integers n.
2. There is a k-string Turing Machine M_f with input and output that, given
an input of length n,
(a) outputs ㄇ^f(n) on its output string in time O(n + f(n)), and
(b) uses O(f(n)) space besides its input and output.
PS. ㄇ = output symbol
Show that the set of proper complexity functions is closed under sums (i.e.,
if f and g are proper complexity functions, then f + g is also a proper
complexity function.)
Ans:
Let f and g be two proper complexity functions. Let's notice that
1. For all positive integers n,
(f+g)(n + 1) = f(n + 1) + g(n + 1) ≧ f(n) + g(n) = (f+g)(n)
because f and g are non-decreasing; hence (f+g) is also non-decreasing.
2. Let M_f and M_g be the (k_f)-string and (k_g)-string Turing machines
associated with f and g, respectively. Let's construct a (k_f + k_g)-string
Turing machine called M_(f+g) as follows:
(a) Given an input of length n, M_(f+g) first emulates M_f on it to write
ㄇ^f(n) in the (k_f)th string.
(b) Then M_(f+g) emulates M_g on the original input to write ㄇ^g(n) in the
(k_f + k_g - 1)st string.
(c) Finally, M_(f+g) concatenates the (k_f)th and (k_f + k_g - 1)st strings
and outputs it in the (k_f + k_g)th tape.
From the construction above, we notice that given an input of length n, the
output of M_(f+g) is of length (f+g)(n) = f(n) + g(n). Now, let's notice
that
(a) M_(f+g) runs in time
O(n + f(n) + n + g(n) + f(n) + g(n)) = O(n + f(n) + g(n)).
(b) The maximum space M_(f+g) uses is
O(f(n)) + O(g(n)) = O(f(n) + g(n)).
From the two items above, (f+g) is a proper complexity function, hence the set
of all proper complexity functions is closed under sums.