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.


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

  • $\begingroup$ 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:) $\endgroup$
    – convxy
    Commented Dec 12, 2020 at 15:16
  • $\begingroup$ This is by your assumption. $\endgroup$ Commented Dec 12, 2020 at 15:17

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.