5
$\begingroup$

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

Improve this question
$\endgroup$
5
  • $\begingroup$ 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$. $\endgroup$
    – Dmitry
    Oct 21, 2022 at 2:01
  • $\begingroup$ 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. $\endgroup$
    – Emil Jeřábek
    Oct 21, 2022 at 7:00
  • $\begingroup$ 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. $\endgroup$
    – Jake
    Oct 21, 2022 at 15:07
  • $\begingroup$ 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? $\endgroup$
    – Lieuwe Vinkhuijzen
    Oct 21, 2022 at 19:08
  • 3
    $\begingroup$ @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. $\endgroup$
    – Jake
    Oct 22, 2022 at 0:39

2 Answers 2

Reset to default
4
$\begingroup$

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

Improve this answer
$\endgroup$
3
  • $\begingroup$ 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. $\endgroup$
    – Ryan Williams
    Oct 25, 2022 at 0:52
  • 2
    $\begingroup$ @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. $\endgroup$
    – Wei Zhan
    Oct 25, 2022 at 1:27
  • $\begingroup$ I think I understand now, thanks $\endgroup$
    – Ryan Williams
    Oct 25, 2022 at 1:45
2
$\begingroup$

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

Improve this answer
$\endgroup$

Your Answer

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

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