# Is DSPACE(n) = DSPACE(1.5n)?

From space-hierarchy theorem it is known that if $$f$$ is space-constructible then DSPACE($$2f(n)$$) is not equal to DSPACE($$f(n))$$.

Here, by DSPACE($$f(n))$$ I mean the class of all problems that can be solved in space $$f(n)$$ by a Turing machine with some fixed alphabet. This allows to consider Space-hierarchy theorem with such accuracy.

The standard argument gives multiplicative constant $$2$$: we need space $$f(n)$$ for constructing a calculation of some Turing machine by an universal one. Also we need $$f(n)$$ to solve a problem with halting.

Question: Is DSPACE($$f(n)$$) equal to DSPACE($$\frac{3}{2}f(n)$$)?

• Any reason you are interested in $\frac32$? Would $1+\Omega(1)$ be equally interesting? – Thomas Nov 22 '18 at 1:09
• Why do you think that the space-hierarchy theorem gives $2f(n)$? I suppose that you argue that we need $f(n)$ space for simulation and $\log_{|\Sigma|} |\Sigma|^{f(n)}$ space for counting the number of steps to avoid infinite loops. But in both cases we need to first mark the $f(n)$'th location on the tape (can be done since $f$ is space-constructible) and how would you do the marking? Your argument is OK if you assume that the machines are not allowed to write *'s, but otherwise some further complications are needed. – domotorp Nov 22 '18 at 8:41
• @Thomas Actually I want $1 + o(1)$ – Alexey Milovanov Nov 22 '18 at 8:48

It can be proved that DSPACE$$(f(\frac 32 n))\ne$$ DSPACE$$(f(n))$$ if $$f$$ grows at least linearly by using a simple variant of the standard padding argument. For a language $$L$$, let $$L'=\{x0^{|x|/2}\mid x\in L\}$$.

Claim. $$L\in$$DSPACE$$(f(n))$$ if and only if $$L'\in$$DSPACE$$(f(\frac 23n))$$ if $$f(n)\ge \frac 32n$$.

(My first answer had several incorrect statements, thanks to Emil for spotting this.)

I will first show how to use the claim to prove the hierarchy. Since $$f$$ grows at least linearly, we have DSPACE$$(2f(n))\subset$$DSPACE$$(f(2n))$$. Take a language $$L\in$$DSPACE$$(f(2n))\setminus$$ DSPACE$$(f(n))$$. Using the claim, $$L'\in$$DSPACE$$(f(\frac 43 n))=$$ DSPACE$$(f(n))$$, where the last equality is by the indirect assumption. But then $$L\in$$DSPACE$$(f(\frac 32 n))=$$ DSPACE$$(f(n))$$, where the last equality is again by the indirect assumption, giving a contradiction.

Proof of the claim. If $$L'\in$$DSPACE$$(f(\frac 23 n))$$, then to prove $$L\in$$DSPACE$$(f(n))$$, we just need to write $$|x|/2$$ 0's to the end of the input $$x$$ and simulate the machine that accepted $$L'$$. Since $$f(n)\ge \frac 32 n$$, this won't increase the space we use. (In fact, knowing how many 0's to write is not clear at all if $$f$$ is small and we cannot increase the alphabet size - instead, we can use another tape and write on that everything that would come after the end of $$x$$.)

The other direction is just this simple by replacing the 0's with *'s, if we are allowed to write *'s. (See the issues with this in my comment to the question.) If we are not allowed to write stars, then we slightly modify the definition of $$L'$$ as $$L'=\{x10^{|x|/2}\mid x\in L\}$$. Now, instead of writing stars, we keep the original input $$x10^{|x|/2}$$ and work with that. But whenever we reach a 1, we go right until we hit another 1 to check whether it was the end-of-word 1 or not. If we've found another 1, we just go back to our 1. If we haven't, we still go back, but we'll know that it should be treated as a star - if we were to write on it, then we also write a 10 after it to have a new end-of-current-word marker. (In fact, there's also a small catch in this part if $$f$$ is small - how can we check if the input is of the form $$x10^{|x|/2}$$? Without destroying the input, I can only solve this by using multiple heads for small $$f$$.)

• I don’t understand the argument at all. Any way I look at it, the padding construction only shows that if $L\in\mathrm{DSPACE}(f(n))$, then $L'\in\mathrm{DSPACE}(f(\frac23n))$, which is quite different from the claim (mind the location of the $\frac23$). Likewise, the opposite direction is not clear at all as stated, what is only clear to me is that if $L'\in\mathrm{DSPACE}(f(\frac23n))$, then $L\in\mathrm{DSPACE}(f(n)+\frac n2)$. Even if I take the claim at face value, the proof of the main result is wrong: $L\in\mathrm{DSPACE}(2f(n))$ only gives $L'\in\mathrm{DSPACE}(\frac43f(n)+\frac n3))$. – Emil Jeřábek Nov 23 '18 at 9:35
• @Emil You're right. I tried to fix it, does it look any better? – domotorp Nov 23 '18 at 10:25
• It’s not entirely clear to me what machine model you are using, but in the standard model with a read-only input tape whose length does not count towards the space bound, I do not see how to show $L'\in\mathrm{DSPACE}(f(\frac23n))\implies L\in\mathrm{DSPACE}(f(n))$ without at least an $O(\log n)$ space overhead. But all right, now I believe the main result, as long as $f$ is space-constructible. Actually, it should give $\mathrm{DSPACE}(f(n))\subsetneq\mathrm{DSPACE}((1+\epsilon)f(n))$ for any constant $\epsilon>0$ by iterating the argument. – Emil Jeřábek Nov 23 '18 at 15:39
• @Emil I don't think the input tape is read-only - AFAIK that is only assumed if $f(n)<n$. – domotorp Nov 23 '18 at 19:51