课程名称︰资讯工程理论基础
课程性质︰选修
课程教师︰吕育道
开课学院：电资学院
开课系所︰资工系
考试日期（年月日）︰2014.12.16
考试时限（分钟）：180
试题 :
Theory of Computation
Midterm Examination on December 16, 2014
Fall Semester, 2014
Problem 1 (25 points)
Let G(V, E) be a directed graph with vertices V and edges E, and |V| be the
number of vertices in G. HAMILTONIAN CYCLE asks if there is a cycle through a
graph G which visits each vertex exactly once. It is known that HAMILTONIAN
CYCLE is NP-complete. BIGCYCLE asks if G has a cycle of length equal or larger
than |V|/2. Reduce HAMILTONIAN CYCLE to BIGCYCLE.
Ans:
Let N be an NTM which decides BIGCYCLE. Construct an NTM M which decides
HAMILTONIAN CYCLE as follows:
1: On input G(V, E) with |V|.
2: Add exactly |V| isolated vertices to G to obtain G'.
3: Run N(G').
4: If N accepts, halt and accept.
5: Otherwise, halt and reject.
Clearly G ∈ HAMILTONIAN CYCLE if and only if G' ∈ BIGCYCLE. M clearly runs
in polynomial time. It completes the proof.
Problem 2 (25 points)
Let a, b, n, m be any odd integers. Show that if gcd(ab, nm) = 1, then
(ab^2 | nm^2) = (a | n). (Recall that (ab | m) = (a | m)(b | m) when
gcd(ab, m) = 1 and (a | nm) = (a | n)(a | m) when gcd(a, nm) = 1.)
Ans:
(ab^2 | nm^2) = (a | nm^2)(b^2 | nm^2)
= (a | n)(a | m^2)(b | nm^2)(b | nm^2)
= (a | n)(a | m)(a | m)(b | nm^2)^2
= (a | n)(a | m)^2
= (a | n)
Problem 3 (25 points)
Show that if 3-SAT has uniform polynomial circuits, then NP = coNP.
Ans:
By Theorem 74 (see p.613 in the slides), 3-SAT is then in P. As 3-SAT is
NP-complete, by Corollary 29 (see p.292 in the slides) P = NP = coNP.
Problem 4 (25 points)
Show that RP is closed under union. (This means that L_1∪L_2 ∈ RP if
L_1 ∈ RP and L_2 ∈ RP. Recall that the error probability does not have to be
exactly 1/2; any constant will do.)
Ans:
Let L_1 and L_2 ∈ RP be decided by polynomial-time Monte Carlo TMs N_1 and
N_2, respectively. Note that for i = 1, 2, and ε_i = 1/2,
Pr(N_i(x) = 1 | x ∈ L_i) ≧ 1 - ε_i and Pr(N_i(x) = 1 | x !∈ L_i) = 0.
To show that RP is closed under union, let TM N_∪ simulate N_1 and N_2 with
independent coin flips on input x. N_∪(x) = 1 if N_1 or N_2 accepts x;
otherwise, N_∪(x) = 0. Now we prove that N_∪ decides L_1∪L_2 with one-sided
error probability ε = ε_1 ε_2. Note that 0 ＜ ε ≦ 1. Assume
x ∈ L_1∪L_2. Then
Pr(N_∪(x) = 1) ＝ 1 - Pr(N_∪(x) = 0)
＝ 1 - Pr(N_1(x) = 0) × Pr(N_2(x) = 0)
≧ 1 - ε_1 ε_2
＝ 1 - ε
Hence ε = 1/4. Now assume x !∈ L_1∪L_2. This implies that
Pr(N_1(x) = 1) = Pr(N_2(x) = 1) = 0. So,
Pr(N_∪(x) = 1) ＝ 1 - Pr(N_∪(x) = 0)
＝ 1 - Pr(N_1(x) = 0) × Pr(N_2(x) = 0)
＝ 1 - (1 - Pr(N_1(x) = 1)) × (1 - Pr(N_2(x) = 1))
＝ 0
Clearly, L_1∪L_2 ∈ RP, and the claim holds.