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

<p><strong>Claim.</strong> <span class="math-container">$L\in$</span><strong>DSPACE</strong><span class="math-container">$(f(n))$</span> if and only if <span class="math-container">$L'\in$</span><strong>DSPACE</strong><span class="math-container">$(f(\frac 23n))$</span> if <span class="math-container">$f(n)\ge \frac 32n$</span>.</p>

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

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

<p><strong>Proof of the claim.</strong>
If <span class="math-container">$L'\in$</span><strong>DSPACE</strong><span class="math-container">$(f(\frac 23 n))$</span>, then to prove <span class="math-container">$L\in$</span><strong>DSPACE</strong><span class="math-container">$(f(n))$</span>, we just need to write <span class="math-container">$|x|/2$</span> 0's to the end of the input <span class="math-container">$x$</span> and simulate the machine that accepted <span class="math-container">$L'$</span>.
Since <span class="math-container">$f(n)\ge \frac 32 n$</span>, this won't increase the space we use.
(In fact, knowing how many 0's to write is not clear at all if <span class="math-container">$f$</span> 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 <span class="math-container">$x$</span>.)</p>

<p>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 <span class="math-container">$L'$</span> as <span class="math-container">$L'=\{x10^{|x|/2}\mid x\in L\}$</span>.
Now, instead of writing stars, we keep the original input <span class="math-container">$x10^{|x|/2}$</span> 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 <span class="math-container">$f$</span> is small - how can we check if the input is of the form <span class="math-container">$x10^{|x|/2}$</span>? Without destroying the input, I can only solve this by using multiple heads for small <span class="math-container">$f$</span>.)</p>

CC BY-SA 4.0
2018-11-23T09:35:45.303Z
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
CC BY-SA 4.0
2018-11-23T10:25:52.903Z
@Emil You're right. I tried to fix it, does it look any better?
domotorp
CC BY-SA 4.0
2018-11-23T15:39:10.610Z
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
CC BY-SA 4.0
2018-11-23T19:51:39.980Z
@Emil I don't think the input tape is read-only - AFAIK that is only assumed if $f(n)<n$.
domotorp
CC BY-SA 4.0
2018-11-22T20:21:35.333Z
2018-11-23T10:24:47.590Z
2018-11-23T10:24:47.590Z
domotorp
<p>From space-hierarchy theorem it is  known that if <span class="math-container">$f$</span> is space-constructible then
<strong>DSPACE</strong>(<span class="math-container">$2f(n)$</span>) is not equal to <strong>DSPACE</strong>(<span class="math-container">$f(n))$</span>. </p>

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

<p>The standard argument gives multiplicative constant <span class="math-container">$2$</span>: we need space <span class="math-container">$f(n)$</span> for constructing a calculation of some Turing machine by an universal one. Also we need <span class="math-container">$f(n)$</span> to solve a problem with halting. </p>

<p><strong>Question:</strong> Is <strong>DSPACE</strong>(<span class="math-container">$f(n)$</span>) equal to <strong>DSPACE</strong>(<span class="math-container">$\frac{3}{2}f(n)$</span>)?   </p>

CC BY-SA 4.0
2018-11-22T01:09:54.910Z
Any reason you are interested in $\frac32$? Would $1+\Omega(1)$ be equally interesting?
Thomas Steinke
CC BY-SA 4.0
2018-11-22T08:41:29.707Z
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
CC BY-SA 4.0
2018-11-22T08:48:08.460Z
@Thomas Actually I want $1 + o(1)$
Alexey Milovanov
CC BY-SA 4.0
2023-10-13T23:20:31.003Z
For a careful argument along these lines, see this paper: https://www.sciencedirect.com/science/article/pii/S0022000077800421  In it, Seiferas fixes the number of tape symbols, and also the number of heads per tape.  Theorem U-2-D (based on Theorem 5) gets a separation by increasing the space bound by a factor of 10, not 2.  I'm not aware of anything that was published improving this bound.
Eric Allender
<cc.complexity-theory><complexity-classes>
Is DSPACE(n) = DSPACE(1.5n)?
Alexey Milovanov
# Is DSPACE(n) = DSPACE(1.5n)?

(Asked by: username_0 on 2018-11-21)

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)$)?

**Tags:** cc.complexity-theory, complexity-classes

> **Comments:**
> **username_1**: Any reason you are interested in $\frac32$? Would $1+\Omega(1)$ be equally interesting?  
> **username_2**: 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.  
> **username_0**: @Thomas Actually I want $1 + o(1)$  
> **username_3**: For a careful argument along these lines, see this paper: https://www.sciencedirect.com/science/article/pii/S0022000077800421  In it, Seiferas fixes the number of tape symbols, and also the number of heads per tape.  Theorem U-2-D (based on Theorem 5) gets a separation by increasing the space bound by a factor of 10, not 2.  I'm not aware of anything that was published improving this bound.  

---

## 1 answers

### Answer by username_2 on 2018-11-22. Score: 9 | Accepted answer

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$.)

> **Comments:**
> **username_4**: 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))$.  
> **username_2**: @Emil You're right. I tried to fix it, does it look any better?  
> **username_4**: 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.  
> **username_2**: @Emil I don't think the input tape is read-only - AFAIK that is only assumed if $f(n)<n$.  

---

