课程名称︰资讯工程理论基础
课程性质︰必修
课程教师︰吕育道
开课学院：电资学院
开课系所︰资工系
考试日期（年月日）︰2014.01.07
考试时限（分钟）：180
是否需发放奖励金：是
（如未明确表示，则不予发放）
试题 :
Theory of Computation
Final Examination on January 7, 2014
Fall Semester, 2013
Problem 1 (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 modulep,
│
╰ -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 all the steps leading to your
answer.
Ans: (1234 | 99) = (46 | 99) = (46 | 9) (46 | 11) = (1 | 9) (2 | 11)
(11^2 - 1)/8
= 1 * (-1)
15
= (-1) = -1
Problem 2 (25 points)
Show that if SAT has no polynomial circuits, then coNP ≠ BPP. (Hint: Adleman's
theorem states that all languages in BPP have polynomialcircuits.)
Ans: Assume that SAT has no polynomial circuits. As all languages in BPP have
polynomial circuits by Adleman's theorem, NP ≠ BPP. Hence
coNP ≠ coBPP = BPP.
Problem 3 (25 points)
Consider the sequence a_1, a_2, ... defined by
n n n
a_n = 2 + 3 + 6 - 1 (n = 1, 2, ...)
Determine all positive integers that are relatively prime to every term of
the sequence. (Hint: Fermat's little theorem says that for all 0 < a < p,
a^(p-1) ≡ 1 mod p.)
Ans:
p-2 p-2 p-2
If p > 3 is a prime, then a_(p-2) = 2 + 3 + 6 ≡ 1 (mod p). To see
this, multiply both sides by 6 to get
p-1 p-1 p-1
3 * 2 + 2 * 3 + 6 ≡ 6 (mod p)
which is a consequence of Fermat's little theorem. Therefore p divides a_(p-2).
Also 2 divides a_1 and 3 divides a_2. So there is no number other than 1 that
is relatively prime to all the terms in the sequence.
Problem 4 (25 points)
Let G = (V, E) be an undirected graph in which every node has a degree of at
most k. Let I be a nonempty set. I is said to be independent if there is no
edge between any two nodes in I. k-DEGREE INDEPENDENT SET asks if there is an
independent set of size k. Consider the following algorithm for k-DEGREE
INDEPENDENT SET:
1: I := ψ;
2: while ∃v ∈ G do
3: Add v to I;
4: Delete v and all of its adjacent nodes from G;
5: end while;
6: return I;
Show that this algorithm fork-DEGREE INDEPENDENT SET is a
(k/(k+1))-approximation algorithm. Recall that an ε-approximation algorithm
returns a solution that is at least (1 - ε) times the optimum for
maximization problems.
Ans:
Since each stage of the algorithm adds a node to I and deletes at most k + 1
nodes from G, I has at least (|V| / (k+1)) nodes, which is at least 1/(k+1)
times the size of the optimum independent set because the size of the optimum
independent set is trivially at most |V|. Thus this algorithm returns
solutions that are never smaller than 1 - 1/(k+1) = k/(k+1) times the optimum.