Question 9.15: Define pad as in Problem 9.13. a. Prove that for every A and...
Define pad as in Problem 9.13.
a. Prove that for every A and natural number k, A ∈ P iff pad (A,n^{k}) \in P.
b. Prove that P ≠ SPACE(n).
(a) Let A be any language and k ∈ N. If A ∈ P, then pad (A,n^{k}) \in P because you can determine whether w ∈ pad (A,n^{k}) by writing w as s\# ^{l} where s doesn’t contain the # symbol, then testing whether \left|w\right| = \left|s\right| ^{k} ; and finally testing whether s ∈ A.
Implementing the first test in polynomial time is straightforward. The second test runs in time poly(|s|), and because |s| ≤ |w|, the test runs in time poly(|w|) and hence is in polynomial time. If pad (A,n^{k}) \in P then A ∈ P because you can determine whether w ∈ A by padding w with # symbols until it has length |w|k and then testing whether the result is in pad (A,n^{k}). Both of these actions require only polynomial time.
(b) Assume that P = SPACE(n). Let A be a language in SPACE (n^{2}) but not in SPACE(n) as shown to exist in the space hierarchy theorem. The language pad (A,n^{2}) ∈ SPACE(n) because you have enough space to run the O(n^{2}) space algorithm for A, using space that is linear in the padded language. Because of the assumption, pad (A,n^{k}) \in P, hence A ∈ P by part (a), and hence A ∈ SPACE(n), due to the assumption once again. But that is a contradiction.