Question

Prove that NTIME(n)$\mathit{\Phi }$PSPACE.

Short answer

NTIME (n) is strict subset of PSPACE (n).

At most t(n) tape cells on each branch can be used by any Turning machine that operates in time t(n) on each computation branch. So, it can be stated that NTIME $\Phi$NSPACE (n).

Step-by-step solution

Considering the Savitch’s theorem

Now, consider the Savitch’s theorem which says that: “Let $f:N\to R$

be a function with $f\left(n\right)\ge n$then NSPACE(f(n)) SPACE((f(n))²). Therefore according to Savitch’s theorem NTIME (n)$⊑$ PSPACE(n²).

Considering the space hierarchy theorem

Now, consider the space hierarchy theorem which says that “if g is space-constructible (1ⁿ 1^g(n) can be computed in space o(g(n))), f(n)=o(g(n)) then SPACE(f (n)) $\Phi$SPACE(g(n)).

Therefore, according to space hierarchy theorem it can be said that SPACE(n²) $\Phi$SPACE(n³). The result follows because SPACE(n³)$⊑$ PSPACE.

Hence NTIME (n)$\Phi$PSPACE(n).