程序代写代做代考 algorithm hmwk5.dvi

hmwk5.dvi

COMS 4236 Homework 5

Mengqi Zong < mz2326@columbia.edu >

April 6, 2018

Problem 1

1. Here is a family of eamples that this algorithm takes exponential time:

E =
m−1∏

i=1

(ai+1xi+1 + aixi)

As we can see, each step we eliminate one pair of parentheses, the size of E doubles.
This is because all the new terms are different. In total, this algorithm takes exponen-
tial time.

2. Guess an assignment X = x1, x2, …, xm that E1 and E2 are different. If E1(X) =
E2(X), then accept. If not, reject.

This algorithm does not place this problem in RP, because in order to make Prob(M
accepts when two equation are equal) greater equal 1/2, we have to try at least 2m−1

different assignments. In this case, the total running time is exponential, not a con-
stant.

This algorithm does not place this problem in coRP, because Prob(M accepts when
two equations are equal) is not 1.

This algorithm does not place this problem in BPP, same reason as that of RP.

1

Question 2

a) 1 ⇒ 2

Since L ∈ RP , we get

∀x ∈ L ⇒ Pr(acc) ≥ 1/2, P r(rej) ≤ 1/2

∀x /∈ L ⇒ Pr(acc) = 0

Since L ∈ coRP , we get

∀x ∈ L ⇒ Pr(acc) = 1, P r(rej) = 0

∀x /∈ L ⇒ Pr(acc) ≤ 1/2, P r(rej) ≥ 1/2

Since L ∈ ZPP = RP ∩ coRP , combine the results together, we get

∀x ∈ L ⇒ Pr(Y es) ≥ 1/2, P r(No) = 0

∀x /∈ L ⇒ Pr(Y es) = 0, P r(No) ≥ 1/2

Add Pr(?), we get

∀x ∈ L ⇒ Pr(Y es) ≥ 1/2, P r(No) = 0, P r(?) ≤ 1/2

∀x /∈ L ⇒ Pr(Y es) = 0, P r(No) ≥ 1/2, P r(?) ≤ 1/2

b) 2 ⇒ 3

We can run the Turing Machine M in part two n times. If in the n times, there is at
least one “Yes”, we accept. If not, we reject. As a result, we get

∀x ∈ L ⇒ Pr(Y es) ≥ 1− 2−n, P r(No) = 0, P r(?) ≤ 2−n

∀x /∈ L ⇒ Pr(Y es) = 0, P r(No) ≥ 1− 2−n, P r(?) ≤ 2−n

c) 3 ⇒ 1

2

From part 3, since

∀x ∈ L ⇒ Pr(Y es) ≥ 1− 2−n ≥ 1/2

∀x /∈ L ⇒ Pr(Y es) = 0

So L ∈ RP . Since

∀x ∈ L ⇒ Pr(No) = 0

∀x /∈ L ⇒ Pr(No) ≥ 1− 2−n, P r(?) ≤ 2−n

we get

∀x ∈ L ⇒ Pr(Y es) = 1

∀x /∈ L ⇒ Pr(No) ≤ 1− 2−n ≤ 1/2, P r(?) ≤ 2−n

So L ∈ coRP .

To sum up, L ∈ ZPP = RP ∩ coRP .

Question 3

a) If L is in ZPP, then it is decided by a probabilistic Turing Machine N that runs in
expected polynomial time.

From condition 3 of Problem 2 , we know that if L is in ZPP, there is a probabilistic
Turing Machine M which runs in polynomial time and return either “Yes” or “No” or
“?” such that

∀x ∈ L ⇒ Pr(Y es) ≥ 1− 2−n, P r(No) = 0, P r(?) ≤ 2−n

∀x /∈ L ⇒ Pr(Y es) = 0, P r(No) ≥ 1− 2−n, P r(?) ≤ 2−n

So, the probability of M giving an correct answer is Prs ≥ 1− 2
−n. Let TM(x) denote

the time that M runs once on input x, then we get

3

TN(x) = Prs · TM(x) + (1− Prs)Prs · 2TM(x) + (1− Prs)
2Prs · 3TM(x) + …

= PrsTM(x)(1 + 2(1− Prs) + 3(1− Prs)
2 + 4(1− Prs)

3 + …)

Let q = (1− Prs) ≤ 2
−n, S = 1 + 2q + 3q2 + 4q3 + …. Since q < 1, we can get qS = q + 2q2 + 3q3 + 4q4 + ... (1− q)S = 1 + q + q2 + q3 + ... ≤ 1 1− q S ≤ 1 (1− q)2 Using the last inequality, we then get TN(x) = PrsTM(x)(1 + 2(1− Prs) + 3(1− Prs) 2 + 4(1− Prs) 3...) ≤ PrsTM(x) (1− (1− Prs))2 = PrsTM(x) Pr2s = TM(x) Prs ≤ P (|x|) So, M is the Turing Machine we are looking at. b) If L can be decided by a probabilistic Turing Machine N that runs in expected polynomial time, then L is in ZPP. If L can be decided by a probabilistic Turing Machine N that runs in expected polyno- mial time, then it means every computation of N terminates with the correct answer Yes or No. Let p denote the probability of Turing Machine N giving an correct answer in the polynomial time P (|x|). Let Prs denote the probability of M giving an correct answer, then we get 4 Prs = 1− (1− p) m ≥ 1 2 (1− p)m ≤ 1 2 m ≥ log1−p 1 2 m ≥ − log1−p 2 m ≥ − log2 2 log2 (1− p) m ≥ − 1 log2 (1− p) As we can see, in order to make Prs greater than 1/2, we must run the Turing Machine at least m · P (|x|) time. That is, (− 1 log 2 (1−p) ) · P (|x|). If the M runs longer than this time, we can terminate the computation and note the result as “?”. Still, we can get Prs ≥ 1/2. In this case, we get ∀x ∈ L ⇒ Pr(Y es) ≥ 1/2, P r(No) = 0, P r(?) ≤ 1/2 ∀x /∈ L ⇒ Pr(Y es) = 0, P r(No) ≥ 1/2, P r(?) ≤ 1/2 That is, L is in ZPP. To sum up, L is in ZPP, if and only if it is decided by a probabilistic Turing Machine N that runs in expected polynomial time. Question 4 1. From A ≤Tp B, we know that A = L(M B). From B ≤Tp C, we know that B = L(MC). Then A = L(ML(M C)). Since polynomial times polynomial is still polynomial, A = L(MC). That is, A ≤TP C. 2. a) P is closed under Cook reductions. This has been shown in the class , P P = P . 5 b) NP is closed under Cook reductions. Since B is in NP, we know that B can be verified in polynomial time. Since polynomial times polynomial is still polynomial, then we can verify A in polynomial time. So A is in NP. c) coNP is closed under Cook reductions. Since B is in coNP, we know that B can be verified in polynomial time. Since polynomial times polynomial is still polynomial, then we can verify A in polynomial time. So A is in coNP. d) Delta2 is closed under Cook reductions. ∆2 = P Σ1 = PNP . And P∆2 = P P NP = PNP . Since B is in ∆2, then A is also in ∆2. e) PH is closed under Cook reductions. PH = ⋃ ∆i = ⋃ PΣi−1 . So P PH = ⋃ P P Σi−1 = PΣi−1 . Since B is in PH, then A is also in PH. f) PSPACE is closed under Cook reductions. We know that B is in PSPACE. Polyno- mial time Polynomial is still polynomial, so A is also in PSPACE. Question 5 a) NP ⊆ NPNP∩coNP We know that NP = NP P . Since P ⊆ NP ∩ coNP , we get NP ⊆ NPNP∩coNP . b) NPNP∩coNP ⊆ NP L ∈ NP ∩ coNP means that ∀x ∈ L, x can be verified in poly-time using a NTM ∀x /∈ L, x can be verified in poly-time using a NTM In this case, any input x ∈ L can be verified in poly-time using a NTM. Then for L′ ∈ NPNP∩coNP , any input x′ ∈ L′ can be verified in poly-time using a NTM. Be- cause polynomial times polynomial is still a polynomial. So we get NPNP∩coNP ⊆ NP . To sum up, NPNP∩coNP = NP . 6