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