2
$\begingroup$

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.

$\endgroup$
3
$\begingroup$

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.

$\endgroup$
2
  • $\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 Dec 12 '20 at 15:16
  • $\begingroup$ This is by your assumption. $\endgroup$ – Yuval Filmus Dec 12 '20 at 15:17

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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