CSC363: Assignment #4
Due on Friday, March 26, 2021 by 11:59pm
Total Marks: 20 (+4)
Question 1
(4 marks) Prove that a polynomial function f(n) of degree d is in O(nd).
(Hint: Write out f(n) = aknk + ak−1nk−1 + . . . + a1n + a0, where k is the degree of f. Let c = ki=0 |ak| and n0 = 1.)
Question 2
(Designed by Paul, 4 marks) Let A, B ⊆ Σ∗ be languages. Define the concatenation of A and B to be
AB={w∈Σ∗ :w=w1w2 forsomew1 ∈Aandw2 ∈B}. For example, if A = {“sushi”, “chungus”} and B = {“juice”, “fish”}, then
AB = {“sushijuice”, “sushifish”, “chungusjuice”, “chungusfish”}.
Show that if A, B ∈ P, then AB ∈ P as well, by constructing a poly-time Turing machine that decides whether a given string is in AB. You may use pseudocode as long as you briefly justify its runtime.
Question 3
(Designed by Eric, 3 marks) Let A, B ⊆ Σ∗ be languages.
Show that if A ∈ P, and B is neither empty nor all of Σ∗, then A ≤p B. You may use pseudocode as long as you briefly justify its runtime.
Question 4
(Designed by Yousef, 6 marks) Let A, B ⊆ Σ∗ be languages.
We say A ≤pT B if there is a B-oracle poly-time Turing machine1 M such that M(x) accepts if
and only if x ∈ A. In this case, we say A is polynomial-time Turing reducible to B.2 Define
LOOP = {(M, w1, w2, w3) : M is a Turing machine that doesn’t halt on at least 2 of the wi } and
HP = {(M, w) : M is a Turing machine that doesn’t halt on w}.
(a) (0 marks) Guess what HP stands for. You may ask your friends (or the internet). (b) (3 marks) Show that LOOP ≤pT HP.
(c) (3 marks) Show that HP ≤pT LOOP.
You may use pseudocode as long as you briefly justify its runtime.
1That is, the number of times we ask “is this in B?” is polynomial, and the rest of the machine runs in polynomial time as well.
2ThisisanalogoustoTuringreducibility.A≤T Bsays“givenanoracletoB,wecancomputeA”.A≤pT Bsays “given an oracle to B (and assuming this oracle takes O(1) time to decide whether something is in B or not), we can compute A in polynomial time”.
The difference between ≤pT and ≤p is analogous to the difference between ≤T and ≤m. In general, to prove A ≤p B, one can describe a polynomial-time procedure to check if something is in A, given access to an oracle for B (which can be assumed to run in O(1) time).
Question 5
(Designed by Daniel, 3 marks + 4 bonus marks) You will apply everything you have learned in this course up until now to the field of cryptography. If you accept the challenge, then you will prove a weaker version of the following claim:
If P = NP then there are no pseudorandom number generators.
Formally, a number generator G is a poly-time computable function (where n is a variable): G : {0, 1}n → {0, 1}n+1
G takes in a n-bit string and extends it to a (n + 1)-bit string3, for any n ∈ N. Now let D be a Turing machine that halts on all inputs. We define the following:
• pD (n) is the probability that if an input x ∈ {0, 1}n is randomly generated, and D is given G(x) as input, then D accepts. In other words, pD(n) is the probability that if we feed D a string from our number generator, it will accept.
• rD(n) is the probability that if an input α ∈ {0,1}n+1 is randomly generated, and D is given α as input, then D accepts. In other words, rD(n) is the probability that if we feed D a truly random string of length n + 1, it will accept.
We say that G is pseudorandom4 if for every deterministic poly-time Turing machine D and every c > 0, for large enough5 n we have
|pD(n)−rD(n)|≤ 1. nc
This is saying that as the size of the input gets larger, no (reasonably efficient) Turing machine can distinguish a pseudo-randomly generated string from a truly random string with a signifi- cant success rate.
Consider the language LG = {G(x) : x ∈ {0, 1}∗}, and notice that LG = range(G), which is the set of all strings that can be outputted by G. You can also partition the language LG into infinitely many finite sets based on the length of the input. This may be useful to you when answering these questions.
(a) (3 marks) Consider the number generator which bit shifts the input to the left once: F(x) = x0
Show that F is not pseudorandom.
(b) (Bonus 4 marks, you should finish the other questions first before attempting) Let H : {0, 1}n → {0, 1}n+1 be some arbitrary number generator. Show that if P = NP then H is not pseudorandom.
We suggest you break it up into three parts: i) Show that LH ∈ NP.
ii) Use the assumption to obtain a deterministic poly-time Turing Machine D that de- cides LH .
iii) Show that H is not pseudorandom using D.
3In the complete definition, a number generator can output a string of any length with the condition that it is longer than the input, and the output length is polynomial to the input length. We are keeping things relatively simple for this question by restricting the output to be exactly one more bit than the input, thus restricting the range.
4In our definition of a pseudorandom number generator, this might be called a Cryptographically Secure Pseudo- Random Number Generator in other resources, or CSPRNG for short, if this interests you further. We are using the asymptotic setting in our definition.
5By this we mean there is some n0 ∈ N so that for all n ≥ n0, the following statement holds.