Prove that NTIME(n) ⊊ PSPACE.

Question

Prove that [latex]NTIME(n) \subsetneq SPACE[/latex].

Accepted Answer

[latex]NTIME(n)\subseteq NSPACE(n)[/latex] because any Turing machine that operates in time t(n) on every computation branch can use at most t(n) tape cells on every branch. Furthermore, [latex]NSPACE(n)\subseteq SPACE(n^{2} )[/latex] due to Savitch’s theorem. However, [latex] SPACE(n^{2} )\subsetneq SPACE(n^{3} )[/latex] because of the space hierarchy theorem. The result follows because [latex]SPACE(n^{3} )\subseteq PSPACE[/latex].

Question 9.3: Prove that NTIME(n) ⊊ PSPACE.

Related Answered Questions

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

Verified Answer:

Give regular expressions with exponentiation that generate the following languages over the alphabet {0,1}. a. All strings of length 500 b. All strings of length 500 or less c. All strings of length 500 or more d. All strings of length different than 500 ...

Verified Answer:

Prove that TIME(2^n) ⊊ ( TIME(2^2n). ...

Verified Answer:

Prove that TIME(2^n) = TIME(2^n+1). ...

Verified Answer: