Define pad as in Problem 9.13.

a. Prove that for every A and natural number k, A ∈ P iff pad(A, n^k) ∈ P.

b. Prove that P ≠ SPACE(n).

Problem 9.13

Consider the function pad : Σ^* × N → Σ^*#^* that is defined as follows. Let pad(s, l) = s^#j , where j = max(0, l−m) andm is the length of s. Thus, pad(s, l) simply adds enough copies of the new symbol # to the end of s so that the length of the result is at least l. For any language A and function f : N → N, define the language pad(A, f) as

pad(A, f) = {pad(s, f(m))| where s ∈ A and m is the length of s}.

Prove that if A ∈ TIME(n⁶), then pad(A, n²) ∈ TIME(n³).