Description
Problem 1 (20 points)
(a) (10 points) Prove that n! ∈ O(n
n
).
(b) (10 points) Which of the following relations is true and which is
false?
(b1) (2 points) n ∈ O((lg n)
3
)
(b2) (2 points) (lg n)
3 ∈ o(n)
(b3) (2 points) n
lg n ∈ O(2
n lg n
)
(b4) (2 points) n
4 ∈ o(100n
4
)
(b5) (2 points) (lg n)
n ∈ O(
√
2
n)
2 / 7
CS 331: Theory of Computing
Problem 2 (20 points)
Prove that any language in P is polynomial reducible to any
language in P which is not ∅ or Σ
∗
.
Hint: Follow the definitions.
3 / 7
CS 331: Theory of Computing
Problem 3 (20 points)
Let L = {0
i1
j
| i > j}. Show that L ∈ TIME(n lg n).
Hint: Pages 279-280 (3rd Edition) or Pages 251-252 (2nd Edition).
4 / 7
CS 331: Theory of Computing
Problem 4 (20 points)
Prove that Graph Isomorphism is in NP. That is,
GI = {hG, Hi | G, H are isomorphic } ∈ NP.
Two graphs G = hVG, EGi and H = hVH, EHi are isomorphic iff
there is a bijection f : VG → VH such that hv, v
0
i ∈ EG if and only if
hf(v), f(v
0
)i ∈ EH.
5 / 7
CS 331: Theory of Computing
Problem 5 (20 points)
Prove that Double Satisfaction Problem, defined as
SAT2 = {hϕi | ϕ is a 3NF -formula with at least two solutions}
is NP-complete.
Hint: Reduce 3SAT to it.
6 / 7
CS 331: Theory of Computing
Problem 6 (20 points)
Prove that the class P is closed under union and complementation
(10 points for each).
7 / 7
CS 331: Theory of Computing