1
$\begingroup$

Let n be an even integer.

Let I be an input of length n.

Positions start at 0: the first bit is bit 0. The second bit is bit 1. etc.

The decision problem is, "Is bit n/2 equal to 1"?

The input is on a tape.

We have a single pointer to the input. We may move the pointer left or right. We cannot overwrite the input tape.

We have a single working-memory tape to compute with. We have a single pointer to it. We may write a 0 or a 1. We may move the pointer left or right. We may not move to the left of, or overwrite the start symbol of the working-memory tape. The working-memory tape is initialized to either the start symbol or immediately to the right.

Space-complexity is the position of the largest cell we write to. This way we "reuse" space.[1]

One way to decide the problem is with a counter of length O(log(n)): Initialize to 0's, then increment until the counter equals n/2, then check the bit.

That takes O(log(n)) space.

Can we do better? Or is O(log(n)) the best space-complexity we can do?

[1] If space complexity was just the total in-use space at any given point in time, we could "move around" the space we're using, using a larger total range of space, but only a smaller portion at any point in time. Defining space as the max position keeps us from "moving around" the space we're using.

$\endgroup$
  • $\begingroup$ The letter $i$ is usually reserved for indices (or for the square root of $-1$). In this context it is better to use $I$. $\endgroup$ – Yuval Filmus May 7 at 21:28
  • $\begingroup$ @YuvalFilmus Thanks! $\endgroup$ – Words Like Jared May 7 at 23:44
1
$\begingroup$

You can do this using $O(1)$ space, using two pointers. Initially, the first pointer is at the left end of the input, and the second pointer is at its right end. Each round, advance both pointers toward the middle, until they meet. This requires no additional space at all!

(The latter, assuming we can enlarge the tape alphabet. Otherwise we can still make do with constant additional space, by implementing the pointers as spaces.)

| cite | improve this answer | |
$\endgroup$
  • $\begingroup$ Agreed. How does one "know" when the pointers meet? Is that part of the state transition? If the pointer is encoded as a space, are you saying the pointers are moving O(n) space along the input tape? $\endgroup$ – Words Like Jared May 7 at 23:43
  • $\begingroup$ The pointers are implemented on the tape. You’ll notice when they cross. Unfortunately I cannot provide the full details, since I need to leave something for you to do. $\endgroup$ – Yuval Filmus May 8 at 5:05

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.