课程名称︰资讯工程理论基础
课程性质︰必修
课程教师：吕育道
开课学院：电资学院
开课系所︰资工所
考试日期（年月日）︰2012.01.10
考试时限（分钟）：
试题 :
Theory of Computation
Final-Term Examination on January 10, 2012
Fall Semester, 2011
Note: You may use any results proved in class.
Problem 1 (25 points). _
Prove that L is NP-complete if and only if its complement L is coNP-complete.
Ans: => Let L be an NP-complete language; thus L ∈ NP. For all L' ∈ NP, let
R be a reduction form L' to L. Problem instance x ∈ L' <=> R(x) ∈ L.
Equivalently, x !∈ L' <=> R(x) !∈ L (the law of transposition). So
__ _ __ _ _
x ∈ L' <=> R(x) ∈ L. R is a reduction from L' to L. Hence L is
coNP-complete.
_ _ __
<= Let L be a coNP-complete language; thus L ∈ coNP. For all L' ∈ coNP,
__ _
let R be a reduction form L' to L. Problem instance
__ _ __ _
x ∈ L' <=> R(x) ∈ L. Equivalently, x !∈ L' <=> R(x) !∈ L (the law
of transposition). So x ∈ L' <=> R(x) ∈ L. R is a reduction from L'
to L. Hence L is NP-complete.
Problem 2 (25 points).
The Jacobi symbol (a | m) is the extension of the Legendre symbol (a | p),
where p is an odd prime, and
╭ 0 if (p | a),
(a | p) = ┤ 1 if a is a quadratic residue module p,
╰ -1 if a is a quadratic nonresidue module p.
k
Recall that when m > 1 is odd and gcd(a, m) = 1, then (a | m) = Π (a | p_i).
i=1
Please calculate (1234 | 99). Please write down the steps leading to your
answer.
Ans: (1234 | 99) = (46 | 99) = (46 | 9)(46 | 11) = (1 | 9)(2 | 11)
(11^2 - 1)/8 15
= 1·(-1) = (-1) = -1
Problem 3 (25 points).
Let μ ≡ E[X] and σ^2 ≡ E[(X - μ)^2] be finite. Show that
prob[|X - μ| ≧ kσ] ≦ 1/(k^2), for k ≧ 0.
(Hints: The Markov inequality says: prob[Y ≧ m] ≦ E[Y]/m if random
variable Y takes on only nonnegative values and m ≧ 0. Try Y = (X - μ)^2.)
Ans: Let Y = (X - μ)^2 and m = (kσ)^2. Then
prob[Y ≧ m] ≦ E[Y]/m
2 2 σ^2
<=> prob[(X - μ) ≧ (kσ) ] ≦ ─────
(kσ)^2
__________ _______ σ^2
<=> prob[√(X - μ)^2 ≧ √(kσ)^2] ≦ ─────
(kσ)^2
1
<=> prob[|X - μ| ≧ kσ] ≦ ───
k^2
The last line is due to Markov's inequality because (X - μ)^2 is a
nonegative value and (kσ)^2 ≧ 0.
Problem 4 (25 points).
Please define RP and prove that RP ⊆ NP.
Ans: RP is the class of all languages L with a (precise) polynomial-time
Monte Carlo TM M such that
If x ∈ L, then Prob[M(x) = "Yes"] ≧ 1/2. (1)
If x !∈ L, then Prob[M(x) = "No"] ＝ 1.
If L in RP and x ∈ L, then there exists a sequence of coin flips f such
that M accepts x with f as the nondeterministic choices by (1).
If x !∈ L, the Prob[M(x) = "Yes"] = 0. So M rejects x. So L ∈ NP.