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.

  • 2
    $\begingroup$ 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. $\endgroup$ – David Richerby Jan 19 '18 at 19:24
  • $\begingroup$ 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)$. $\endgroup$ – Yuval Filmus Jan 20 '18 at 16:17
  • $\begingroup$ If you actually try to work out the proof, you'll see what goes wrong. $\endgroup$ – Yuval Filmus Jan 20 '18 at 16:18
  • $\begingroup$ So we're saying that the claim is not true? still not sure I understand $\endgroup$ – Tomer Amir Jan 20 '18 at 17:34

Your Answer

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

Browse other questions tagged or ask your own question.