2
$\begingroup$

I'm trying to prove that $n\log n$ is space constructible. I've already managed to prove that $\log n$ is space constructible, but I cannot figure out how to prove the same about $n$. I assume, that if both $n$ and $\log n$ are space constructible, $n\log n$ will be space constructible as well.

I'm using Sipser's definition of space constructibility:

A function $f\colon N\to N$, where $f(n)$ is at least $O(\log ⁡n)$, is called space constructible if the function that maps the string $1^n$ to the binary representation of $f(n)$ is computable in space $O(f(n))$.

$\endgroup$
  • $\begingroup$ Oh dear. Sipser really does say "at least $O(\log n)$". This is completely meaningless. Every function is at least as big as some function that's no more than $\log n$, since the constant zero function is $O(\log n)$. $\endgroup$ – David Richerby Mar 7 '18 at 13:20
2
$\begingroup$

You are right that if we can construct both $n$ and $\log n$ in $O(n\log n)$ space, we can construct $n\log n$ by multiplying these two values. I think constructing $\log n$ is actually the harder part here, which you seem to have already figured out. But let's go through it.

First, recall that a $k$-tape Turing Machine can be simulated on a single-tape Turing Machine by concatenating all the tapes onto a single tape. I am glossing over the details a bit here (but see Sipser for the details), but the key observation is that the space complexity can equivalently be viewed as the total space used across all tapes of a $k$-tape Turing Machine. So if we can construct a procedure for a $k$-tape Turing Machine that uses $O(n\log n)$ space across all tapes, then we have shown that $n\log n$ is space constructible.

We can construct $\log n$ through repeated halving of $n$. Specifically, we can copy $1^n$ from our initial tape containing the input to a second tape. Then, we can blank half of the ones on this second tape. Once we have blanked half of the ones, this tape will store $1^{n/2}$. We can repeat this halving process until there is only a single $1$ left. We count the number of halvings performed, in binary. We simply maintain a binary counter on a third tape, and perform a binary increment each time we perform a halving on $n$. At the end, the third tape will store the binary representation of $\log n$.

I am assuming that you already had figured the above out since you said you managed to prove $\log n$ is space constructible. And indeed you are correct that if we can independently construct $n$, we can multiply $n$ by $\log n$ in binary, using at most $n\log n$ space (in fact we will need less). All we really need then is to write out the binary representation of $n$ to another tape. Recall how we convert numbers to binary representation: the least significant bit of the binary representation of $n$ is $n\bmod 2$. Then, we can convert $\lfloor n/2\rfloor$ to binary (in a recursive manner) to compute the remaining bits. So, our Turing Machine will continue as follows: Copy $1^n$ to an available tape. Then, compute $n\bmod 2$. Note that we can do this fairly easily (If you are following Sipser, you should hopefully be comfortable with the fact that the set of all even-length strings is even a regular language). We write out the value of $n\bmod 2$ to another tape (call this the "$n$ tape"). Then, we perform the halving procedure on the $1^n$ again. Here, we should be careful about how we handle the case where $n$ is odd: we round down (For example, if $n=5$, after the halving procedure, the tape should contain $11$, the unary representation of $2$). This is to ensure the halving semantics are consistent with $\lfloor n/2 \rfloor$. Then, we move the head on the "$n$ tape" to the left one space, compute the mod once again, and write the result to the "$n$ tape" again. If we continue this modding and halving, writing the results of the modding to the left of the previously written bits on the "$n$" tape, we will eventually write out the binary representation of $n$ (once the working tape has only a single $1$ on it, the "$n$ tape" will contain the binary representation of $n$).

After these two procedures, we should have $\log n$ on one tape and $n$ on another tape, both in binary. Then, as you have already recognized, we can compute the product in $O(n\log n)$ space.

$\endgroup$
  • $\begingroup$ You need to be very careful about statements like "we can assume that our Turing Machine has multiple tapes". That's true for computability but not for time complexity. You're using the fact that it remains true for space complexity. $\endgroup$ – David Richerby Mar 7 '18 at 13:23
  • $\begingroup$ Good point. I'll update the answer to reflect this. $\endgroup$ – ngrammel Mar 8 '18 at 21:21

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.