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

Question

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.

Answer 1

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.