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

$\endgroup$
  • 2
    $\begingroup$ Any reason you are interested in $\frac32$? Would $1+\Omega(1)$ be equally interesting? $\endgroup$ – Thomas Nov 22 '18 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 Nov 22 '18 at 8:41
  • $\begingroup$ @Thomas Actually I want $1 + o(1)$ $\endgroup$ – Alexey Milovanov Nov 22 '18 at 8:48
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$.)

$\endgroup$
  • $\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 Nov 23 '18 at 9:35
  • 1
    $\begingroup$ @Emil You're right. I tried to fix it, does it look any better? $\endgroup$ – domotorp Nov 23 '18 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 Nov 23 '18 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 Nov 23 '18 at 19:51

Your Answer

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

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