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).

The blue check mark means that this solution has been answered and checked by an expert. This guarantees that the final answer is accurate.
Learn more on how we answer questions.

(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.

Related Answered Questions

Question: 9.3

Verified Answer:

NTIME(n)\subseteq NSPACE(n) because...
Question: 9.2

Verified Answer:

The containment TIME (2^{n}) ⊆ TIME (2^{2n+...
Question: 9.1

Verified Answer:

The time complexity classes are defined in terms o...