# Prove that $\mathsf{P} \neq \bigcup_{k=1}^{\infty}\mathsf{DSPACE}(\log^k n)$

Prove that $$\mathsf{P} \neq \bigcup_{k=1}^{\infty}\mathsf{DSPACE}(\log^k n)$$.
Hint: Assume that there is an equality, show that this implies $$\mathsf{DTIME}(n^{\log n})\subseteq \mathsf{P}$$ via a padding argument.

I proved that $$L'=\{x\#1^{|x|^{\log|x|}}\mid x\in L\}$$ is in $$\mathsf{P}$$ but I'm not sure how to conclude that $$L\in\mathsf{P}$$, or how do I get the contradiction to the assumption.

The proof is by contradiction. We assume that $$\mathsf{P} = \bigcup_{k=1}^\infty \mathsf{DSPACE}(\log^k n)$$, and reach a contradiction.

Let $$L$$ be any language in $$\mathsf{DTIME}(n^{\log n})$$. Thus there is a Turing machine for $$L$$ which runs in time $$n^{C\log n}$$, and in particular, uses space at most $$n^{C\log n}$$. Let $$L' = \{ x10^{|x|^{C\log |x|} - |x| - 1} : x \in L \}$$. Then $$L' \in \mathsf{P}$$, and so $$L' \in \mathsf{DSPACE}(\log^k n)$$, for some $$k$$. In terms of the true input size $$m$$, we have $$n = m^{C\log m}$$, and so $$L \in \mathsf{DSPACE}(\log^k (n^{C\log n})) \subseteq \mathsf{DSPACE}(\log^{2k} n) \subseteq \mathsf{P}$$. This contradicts the time hierarchy theorem.

• Can you please explain why $\mathsf{DSPACE}(\log^{2k} n) \subseteq \mathsf{P}$? We know that $\mathsf{SPACE}(s(n)) \subseteq \mathsf{TIME} (2^{O(s(n))})$, therefore $\mathsf{DSPACE}(\log^{2k} n) \subseteq \mathsf{TIME} (2^{O(\log^{2k} n)})=\mathsf{TIME} (n^ {\log^{2k-1} n})$ and I can't see why this is in P. Thanks:) Commented Dec 12, 2020 at 15:16
• This is by your assumption. Commented Dec 12, 2020 at 15:17