xuebaunion@vip.163.com

3551 Trousdale Rkwy, University Park, Los Angeles, CA

留学生论文指导和课程辅导

无忧GPA：https://www.essaygpa.com

工作时间：全年无休-早上8点到凌晨3点

微信客服：xiaoxionga100

微信客服：ITCS521

程序代写案例-CSE 6321-Assignment 3

时间：2021-04-02

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

学霸联盟

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

学霸联盟