<p>Here is a self-contained proof. Suppose <span class="math-container">$n=2m+1$</span>, and the number of configurations (including the state of the machine and the work tapes but NOT the input tape) is smaller then <span class="math-container">$m$</span>. Refuting this implies that the space is at least <span class="math-container">$\Omega(\log n)$</span>.</p>
<p>Consider the input <span class="math-container">$0^m1^m0$</span>. Assume that the head starts at the first cell (position <span class="math-container">$0$</span>), and moves by at most one cell each time. We divide the execution sequence into stages, cut at every time the head moves across position <span class="math-container">$m-1\mid m$</span> or <span class="math-container">$2m-1\mid 2m$</span> (i.e. the input symbol it points at changes between <span class="math-container">$0$</span> and <span class="math-container">$1$</span>). We only care about stages that start with <span class="math-container">$m-1\rightarrow m$</span> and end with <span class="math-container">$2m-1\rightarrow 2m$</span>, or the other way around, that start with <span class="math-container">$2m\rightarrow2m-1$</span> and end with <span class="math-container">$m\rightarrow m-1$</span>.</p>
<p>Take a such stage between time <span class="math-container">$[t,t')$</span>, where the head at time <span class="math-container">$t$</span> goes from <span class="math-container">$m-1$</span> to <span class="math-container">$m$</span> and at time <span class="math-container">$t'$</span> goes from <span class="math-container">$2m-1$</span> to <span class="math-container">$2m$</span>. For each <span class="math-container">$i\in[m,2m)$</span>, let <span class="math-container">$t_i\in[t,t')$</span> be the first time the head moves to position <span class="math-container">$i$</span>. By pigeonhole's principle, there must be <span class="math-container">$i&lt;j$</span> such that the configurations at time <span class="math-container">$t_i$</span> and <span class="math-container">$t_j$</span> are the same. For each such stage we record the number <span class="math-container">$j-i$</span>, and let <span class="math-container">$L$</span> be a common multiple of these <span class="math-container">$j-i$</span>.</p>
<p>Now we claim that on input <span class="math-container">$0^m1^{m+L}0$</span>, the machine halts with the same configuration as on input <span class="math-container">$0^m1^m0$</span>. This can be proved by induction over the stages and the steps, and can be seen from the following illustration (the blue lines indicate the movement of the head on the input tape, and the purple dots indicate the same configuration):
<a href="https://i.sstatic.net/3i5Y6.png" rel="nofollow noreferrer"><img src="https://i.sstatic.net/3i5Y6.png" alt="enter image description here" /></a>
The reason that the execution sequence between the two purples dots (<span class="math-container">$t_i$</span> and <span class="math-container">$t_j$</span>) is repeated, is because the input symbol is always <span class="math-container">$1$</span>.</p>
<p>On the other hand, <span class="math-container">$\mathsf{MAJ}(0^m1^m0)=0$</span> while <span class="math-container">$\mathsf{MAJ}(0^m1^{m+L}0)=1$</span> for <span class="math-container">$L&gt;1$</span>, leading to a contradiction.</p>

CC BY-SA 4.0
2022-10-25T00:52:41.920Z
Configurations also include the tape head position, and there are already n possibilities for that. This argument does work for an "oblivious" TM (where the head moves in the same pattern on all sequences of length n) such as a streaming algorithm.
Ryan Williams
CC BY-SA 4.0
2022-10-25T01:27:59.417Z
@RyanWilliams The configurations I mentioned here does not include the head position of the input tape, and for space $S$ the head positions on work tapes has only $S^{O(1)}$ possibilities. I added some clarification in my post. Indeed, the whole argument is a basically a pumping lemma on the input tape head positions.
Wei Zhan
CC BY-SA 4.0
2022-10-25T01:45:30.883Z
I think I understand now, thanks
Ryan Williams
CC BY-SA 4.0
2022-10-24T22:29:55.100Z
2022-10-25T01:23:59.890Z
2022-10-25T01:23:59.890Z
Wei Zhan
<p>The naive bound is tight: MAJORITY is a non-regular context-free language, and any machine with <span class="math-container">$o(\log(n))$</span> space cannot recognize such a language even with nondeterminism (source: &quot;A lower bound for the nondeterministic space complexity of context-free recognition&quot; by Alt et al.).</p>

CC BY-SA 4.0
2022-10-24T19:08:27.940Z
2022-10-24T19:08:27.940Z
Jake
<p>MAJORITY is the language of bitstrings where more than half of the bits are 1s. I'm interested in lower bounds in the multitape TM model.</p>
<p>This can be solved in <span class="math-container">$DTISP(O(n), O(\log(n))$</span> with a naive solution: iterate over the input and keep a counter for the number of 1s (as well as the length <span class="math-container">$n$</span> of the input), then compare the number of 1s against <span class="math-container">$n/2$</span>. (Incrementing the counters only takes amortized linear time.)</p>
<p>Certainly the time lower bound is <span class="math-container">$\Theta(n)$</span>, since we have to read all of the input bits. But do we know a <span class="math-container">$\Theta(\log(n))$</span> space lower bound? Or are there known algorithms with better space complexity (perhaps at the expense of time complexity)?</p>

CC BY-SA 4.0
2022-10-21T02:01:47.460Z
Doesn't the naive approach require only $O(n)$ time? Incrementing $n$ times should require $O(n)$ time: the first bit changes $n$ times, the second bit changes $\frac n2$ times, etc., and so the total time is at most $n \sum_{i=0}^{\infty} 2^{-i} = 2n$.
Dmitry
CC BY-SA 4.0
2022-10-21T07:00:45.900Z
The first algorithm takes time $O(n)$ as Dmitry wrote. I frankly do not understand the description of the second algorithm (what is the resetting supposed to achieve, and how it is implemented); just straight taking a counter for the number of 1s and a counter for the number of 0s will again use $O(n)$ time. Perhaps the really naive solution that’s supposed to take time $O(n\log n)$ is that you only have one counter to keep track of the *balance*: then you do both increments and decrements in random order, and this may indeed need time $\Omega(\log n)$ for $\Omega(n)$ of the steps.
Emil Jeřábek
CC BY-SA 4.0
2022-10-21T15:07:31.560Z
Fair points - the linked algorithm is more concerned with having more than 2 voting options, but in the binary case we can ignore that. I'll simplify the exposition in the question.
Jake
CC BY-SA 4.0
2022-10-21T19:08:00.990Z
I seem to recall that a machine using $o(log n/\log\log n)$ and $\omega(1)$ space is not well-behaved in some way. Such a machine cannot remember where on the tape it is, and yet must know _something_ about $n$ since its space usage increases with $n$. Do such machines exist? I don't have a reference handy, but perhaps you have thought about this yourself? Or maybe one of the other contributors can jump in?
Lieuwe Vinkhuijzen
CC BY-SA 4.0
2022-10-22T00:39:43.760Z
@LieuweVinkhuijzen I know any space $o(\log\log(n))$ only accepts regular languages, and MAJORITY is nonregular. So we do know a space $\Omega(\log\log(n))$ lower bound from that.
Jake
<lower-bounds><turing-machines>
Time/space lower bounds on Majority (in the multitape TM model)
Jake
# Time/space lower bounds on Majority (in the multitape TM model)

(Asked by: username_0 on 2022-10-20)

MAJORITY is the language of bitstrings where more than half of the bits are 1s. I'm interested in lower bounds in the multitape TM model.

This can be solved in $DTISP(O(n), O(\log(n))$ with a naive solution: iterate over the input and keep a counter for the number of 1s (as well as the length $n$ of the input), then compare the number of 1s against $n/2$. (Incrementing the counters only takes amortized linear time.)

Certainly the time lower bound is $\Theta(n)$, since we have to read all of the input bits. But do we know a $\Theta(\log(n))$ space lower bound? Or are there known algorithms with better space complexity (perhaps at the expense of time complexity)?

**Tags:** lower-bounds, turing-machines

> **Comments:**
> **username_1**: Doesn't the naive approach require only $O(n)$ time? Incrementing $n$ times should require $O(n)$ time: the first bit changes $n$ times, the second bit changes $\frac n2$ times, etc., and so the total time is at most $n \sum_{i=0}^{\infty} 2^{-i} = 2n$.  
> **username_2**: The first algorithm takes time $O(n)$ as username_1 wrote. I frankly do not understand the description of the second algorithm (what is the resetting supposed to achieve, and how it is implemented); just straight taking a counter for the number of 1s and a counter for the number of 0s will again use $O(n)$ time. Perhaps the really naive solution that’s supposed to take time $O(n\log n)$ is that you only have one counter to keep track of the *balance*: then you do both increments and decrements in random order, and this may indeed need time $\Omega(\log n)$ for $\Omega(n)$ of the steps.  
> **username_0**: Fair points - the linked algorithm is more concerned with having more than 2 voting options, but in the binary case we can ignore that. I'll simplify the exposition in the question.  
> **username_3**: I seem to recall that a machine using $o(log n/\log\log n)$ and $\omega(1)$ space is not well-behaved in some way. Such a machine cannot remember where on the tape it is, and yet must know _something_ about $n$ since its space usage increases with $n$. Do such machines exist? I don't have a reference handy, but perhaps you have thought about this yourself? Or maybe one of the other contributors can jump in?  
> **username_0**: @LieuweVinkhuijzen I know any space $o(\log\log(n))$ only accepts regular languages, and MAJORITY is nonregular. So we do know a space $\Omega(\log\log(n))$ lower bound from that.  

---

## 2 answers

### Answer by username_4 on 2022-10-24. Score: 4 | Accepted answer

Here is a self-contained proof. Suppose $n=2m+1$, and the number of configurations (including the state of the machine and the work tapes but NOT the input tape) is smaller then $m$. Refuting this implies that the space is at least $\Omega(\log n)$.

Consider the input $0^m1^m0$. Assume that the head starts at the first cell (position $0$), and moves by at most one cell each time. We divide the execution sequence into stages, cut at every time the head moves across position $m-1\mid m$ or $2m-1\mid 2m$ (i.e. the input symbol it points at changes between $0$ and $1$). We only care about stages that start with $m-1\rightarrow m$ and end with $2m-1\rightarrow 2m$, or the other way around, that start with $2m\rightarrow2m-1$ and end with $m\rightarrow m-1$.

Take a such stage between time $[t,t')$, where the head at time $t$ goes from $m-1$ to $m$ and at time $t'$ goes from $2m-1$ to $2m$. For each $i\in[m,2m)$, let $t\_i\in[t,t')$ be the first time the head moves to position $i$. By pigeonhole's principle, there must be $i such that the configurations at time $t\_i$ and $t\_j$ are the same. For each such stage we record the number $j-i$, and let $L$ be a common multiple of these $j-i$.

Now we claim that on input $0^m1^{m+L}0$, the machine halts with the same configuration as on input $0^m1^m0$. This can be proved by induction over the stages and the steps, and can be seen from the following illustration (the blue lines indicate the movement of the head on the input tape, and the purple dots indicate the same configuration):
[![enter image description here](https://i.sstatic.net/3i5Y6.png)](https://i.sstatic.net/3i5Y6.png)
The reason that the execution sequence between the two purples dots ($t\_i$ and $t\_j$) is repeated, is because the input symbol is always $1$.

On the other hand, $\mathsf{MAJ}(0^m1^m0)=0$ while $\mathsf{MAJ}(0^m1^{m+L}0)=1$ for $L>1$, leading to a contradiction.

> **Comments:**
> **username_5**: Configurations also include the tape head position, and there are already n possibilities for that. This argument does work for an "oblivious" TM (where the head moves in the same pattern on all sequences of length n) such as a streaming algorithm.  
> **username_4**: @RyanWilliams The configurations I mentioned here does not include the head position of the input tape, and for space $S$ the head positions on work tapes has only $S^{O(1)}$ possibilities. I added some clarification in my post. Indeed, the whole argument is a basically a pumping lemma on the input tape head positions.  
> **username_5**: I think I understand now, thanks  

---

### Answer by username_0 on 2022-10-24. Score: 2

The naive bound is tight: MAJORITY is a non-regular context-free language, and any machine with $o(\log(n))$ space cannot recognize such a language even with nondeterminism (source: "A lower bound for the nondeterministic space complexity of context-free recognition" by Alt et al.).


---

