CSE 6321: Assignment 3
Due: 11:59pm Monday, April 5nd
General rules: If you consult any books or
other sources, you must provide citations for
your sources. If you collaborate with other stu-
dents on any of the problems, you must state it
clearly at the beginning of your solution to the
problem (give name(s) of the collaborator(s)).
Your solutions should be submitted on Carmen
in pdf format (either typed or easy to read hand-
written & scanned).
Write clean and succinctly; solutions will be
graded based on correctness not based on their
volume.
1. (15 points) Recall that
PRIMES = {n | n is a prime number}.
Use the following number theoretic fact to prove that PRIMES ∈ NP: n is a prime number if and only
if n = 2 or there exists a ∈ {2, ..., n− 1}
(i) an−1 = 1 (mod n), and
(ii) a(n−1)/q 6= 1 (mod n) for all prime factors q of n− 1.
2. (20 points) The goal of this problem is to show that NP 6= SPACE(n).
(a) (5 points) For a language L ⊆ {0, 1}∗ and a function f : N → N define the following padded
language
Pad(L, f) = {〈x, 1(f(|x|)−|x|〉|x ∈ L}.
Prove that if f(n) = O(p(n)) for some polynomial p, then Pad(L, f) ∈ NP if and only if L ∈ NP.
(b) (5 points) Prove that if L ∈ SPACE(S(n)) then Pad(L, S) ∈ SPACE(n).
(c) (10 points) Use (a) and (b) along with the space hierarchy theorem to prove that NP 6= SPACE(n).
1
3. (15 points) Recall that ≤l denotes log-space reductions. Prove that
(a) (10 points) A ≤l B and B ≤l C implies A ≤l C.
(b) (5 points) A ≤l B and B ∈ L implies A ∈ L.
4. (10 points) Give a formal proof of Lemma 5.22 from the lecture notes.
5. (15 points) Prove that the following language is in NL.
B := {〈G〉 | G is a bipartite graph}.
6. (25 points) We say that two Boolean formulas φ and ψ over the same set of variables are equivalent,
denoted φ ≡ ψ, if for every input x, φ(x) = ψ(x). For example
(x1 ∨ x2) ∧ x3 ≡ (x1 ∧ x3) ∨ (x2 ∧ x3).
Define
minFormula = {〈φ〉 | φ is a formula, and for every shorter formula ψ,ψ 6≡ φ}
(a) (10 points) Prove that minFormula ∈ PSPACE
(b) (15 points) Prove that if P = NP then minFormula ∈ P.
2










































学霸联盟