11
$\begingroup$

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

Improve this question
$\endgroup$
4
  • 2
    $\begingroup$ Any reason you are interested in $\frac32$? Would $1+\Omega(1)$ be equally interesting? $\endgroup$
    – Thomas Steinke
    Commented Nov 22, 2018 at 1:09
  • 1
    $\begingroup$ 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. $\endgroup$
    – domotorp
    Commented Nov 22, 2018 at 8:41
  • $\begingroup$ @Thomas Actually I want $1 + o(1)$ $\endgroup$
    – Alexey Milovanov
    Commented Nov 22, 2018 at 8:48
  • $\begingroup$ For a careful argument along these lines, see this paper: 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. $\endgroup$
    – Eric Allender
    Commented Oct 13, 2023 at 23:20

1 Answer 1

Reset to default
9
$\begingroup$

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

Improve this answer
$\endgroup$
4
  • $\begingroup$ 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))$. $\endgroup$
    – Emil Jeřábek
    Commented Nov 23, 2018 at 9:35
  • 1
    $\begingroup$ @Emil You're right. I tried to fix it, does it look any better? $\endgroup$
    – domotorp
    Commented Nov 23, 2018 at 10:25
  • 1
    $\begingroup$ 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. $\endgroup$
    – Emil Jeřábek
    Commented Nov 23, 2018 at 15:39
  • 2
    $\begingroup$ @Emil I don't think the input tape is read-only - AFAIK that is only assumed if $f(n)<n$. $\endgroup$
    – domotorp
    Commented Nov 23, 2018 at 19:51

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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