# if $DSPACE(\log^2n) \subseteq NTIME(n^2)$ is $DSPACE(\log^3n) \subseteq NTIME(n^2\log n)$?

I am trying to prove that if $DSPACE(\log^2n) \subseteq NTIME(n^2)$ then $DSPACE(\log^3 n) \subseteq NTIME(n^2\log n)$ using padding, but I'm not sure if the claim is correct, or how to do the padding.

I tried to create for $L \in DSPACE(\log^3 n)$ the language $L_{\mathrm{pad}} = \{ x\#^{\log^3(|x|)-|x|}\mid x \in L\}$ and then show that $L_{\mathrm{pad}} \in DSPACE(\log^2 n)$ but I am not sure that this is right.

From there, I think that the rest is just a standard padding argument proof.

• I'd be very suspicious of that claim. Space is more powerful than time and allowing yourself X amount more space is much more powerful than allowing yourself X amount more time. But, here, you're trying to prove that giving yourself a log-factor more space is not more powerful than giving yourself a log-factor more time. – David Richerby Jan 19 '18 at 19:24
• It's known that $\mathsf{DSPACE}(1) \subseteq \mathsf{NTIME}(n)$, but it is probably not expected that $\mathsf{DSPACE}(\log n) \subseteq \mathsf{NTIME}(n\log n)$. – Yuval Filmus Jan 20 '18 at 16:17
• If you actually try to work out the proof, you'll see what goes wrong. – Yuval Filmus Jan 20 '18 at 16:18
• So we're saying that the claim is not true? still not sure I understand – Tomer Amir Jan 20 '18 at 17:34