课程名称︰资讯工程理论基础
课程性质︰选修
课程教师：吕育道
开课学院：电资学院
开课系所︰资工所
考试日期（年月日）︰2016.01.12
考试时限（分钟）：
试题 :
Theory of Computation
Final Exam, 2015 Fall Semester,
1/12/2016
Note: Unless stated otherwise, you may use any results proved in class.
Problem 1 (25 points)
Reduce 3SAT to INTEGER PROGRAMMING.
Ans: Let the variables in the 3SAT formula be x_1, x_2, …, x_n. We will have
corresponding variables z_1, z_2, …, z_n in our integer program. First,
we restrict each variable z_i such that
0 ≦ z_i ≦ 1, for all i.
Assigning z_i = 1 in the integer program represents setting x_i = true in
the 3SAT formula, and assigning z_i = 0 represents setting x_i = false.
For each clause such as (x_1 Ｖ ﹁x_2 Ｖ x_3), we can rewrite it as the
integer program:
z_1 + (1 - z_2) + z3 > 0.
To satisfy this inequality, we must either set z_1 = 1 or z_2 = 0 or
z_3 = 1, which means we either set x_1 = true or x_2 = false or x_3 = true
in the corresponding truth assignment. Assigning true/false to every x_i
in all clauses, we then will have a set of input of integer programming
that is equivalent to the given set of input to 3SAT.
Problem 2 (25 points)
For the Diffie-Hellman Secret-Key Agreement Protocol, Alice and Bob agree on a
large prime p and a primivite root g of p (where p and g are public). Alice
chooses a random a and Bob also chooses a random b.
1. (10 points) What are the values of α, β and the common key?
2. (15 points) For p = 11, g = 2, a = 4 and b = 5, what are the values of
α, β and the common key?
Ans: 1. The values of α and β are
α ≡ g^a (mod p),
β ≡ g^b (mod p),
and the common key is
α^b ≡ g^(ab) ≡ g^(ba) ≡ β^a (mod p).
2. For p = 11, g = 2, a = 4 and b = 5, the values of α and β are
α ≡ 2^4 ≡ 5 (mod 11),
β ≡ 2^5 ≡ 10 (mod 11),
and the common key is
α^b ≡ 2^(4*5) ≡ β^a ≡ 1 (mod 11).
Problem 3 (25 points)
Prove that NP ⊆ ZPP, then NP ⊆ BPP.
Ans: Assume NP ⊆ ZPP. Pick any NP-complete language L. We only need to show
that L ∈ BPP. There exists an algorithm A that decides L in expected
polynomial time, say p(n). By Markov's inequality, the probability that
the running time of A exceeds 3p(n) is at most 1/3. Run A for 3p(n) steps
to determine with probability at least 1 - 1/3 = 2/3 whether the input
belongs in L. We therefore obtain a polynomial-time algorithm for L which
errs with probability at most 1/3 on each input. Hence L is in BPP.
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 for k-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.
Problem 5 (25 points)
A cut in an undirected graph G = (V, E) is a partition of the nodes into two
nonempty sets S and V - S. MAX BISECTION asks if there is a cut of size at
least K such that |S| = |V - S|. It is known that MAX BISECTION is NP-complete.
BISECTION WIDTH asks if there is a bisection of size at most K such that
|S| = |V - S|. Show that BISECTION WIDTH is NP-complete. You do not need to
show it is in NP.
Ans: See pp. 392-393 in the slides.
Problem 6 (25 points)
Is x^4 ≡ 25 mod 1013 solvable and why?
Ans: Let's first notice that 1013 is a prime. Since 25 has square roots ±5, we
need to check if any of the Legendre symbols (5/1013) or (-5/1013) is 1.
We have
╭ 5 ╮ ╭ 1013 ╮ ╭ 3 ╮
│───│ = │───│ = │──│ = -1
╰ 1013 ╯ ╰ 5 ╯ ╰ 5 ╯
and
╭ -5 ╮ ╭ -1 ╮╭ 5 ╮
│───│ = │───││───│
╰ 1013 ╯ ╰ 1013 ╯╰ 1013 ╯
(1013-1)/2╭ 5 ╮ ╭ 5 ╮
= (-1) │───│ = │───│ = -1
╰ 1013 ╯ ╰ 1013 ╯
so 25 is not a quadratic residue modulo 1013 and cannot be a solution to
x^4 ≡ 25 mod 1013.
Problem 7 (25 points)
Let n ∈ Z+ with n ≧ 2. Let ψ(n) stand for Euler's totient function, which
counts the number of positive integers smaller than n and are relative prime
to n.
1. (5 points) Determine ψ(2^n).
2. (10 points) Determine ψ(ψ(2^n)).
3. (10 points) Determine ψ((2p)^n) where p is an odd prime.
Ans: 1. ψ(2^n) = 2^n - 2^(n-1) = 2^(n-1) (2-1) = 2^(n-1).
2. ψ(ψ(2^n)) = ψ(2^(n-1)) = 2^(n-1) - 2^(n-2) = 2^(n-2) (2-1)
= 2^(n-2).
3. ψ((2p)^n) = ψ((2^n)(p^n)) = ψ(2^n) ψ(p^n) = 2^(n-1) (p^n - p^(n-1))
= 2^(n-1) p^(n-1) (p-1).