I’ve been wondering about the computational complexity of a problem that involves bit shifting.
Let me define some notation before I present the problem. If $\langle{b}\rangle$ is a bitstring representing a natural number $b$, let $\mathsf{shift}(c,\langle{b}\rangle):=\langle\lfloor b \cdot 2^{c}\rfloor\rangle$ for a constant $c\in\mathbb{Z}$. In other words, the function $\mathsf{shift}(c,\bullet)$ performs a bit shift of $c$ steps upward (or $-c$ steps downward, if $c$ is negative).
Let’s say a bit shift function $\mathsf{shift}(c, \bullet)$ is lossless on the bitstring $\langle x\rangle$ if $\mathsf{shift}(-c,\mathsf{shift}(c,x))=\langle x\rangle$. For example, $\mathsf{shift}(-3,\bullet)$ is lossless on $\texttt{101011000}$: $$\texttt{101011}\underbrace{\texttt{000}}\rightarrow\texttt{101011}\rightarrow\texttt{101011}\underbrace{\texttt{000}}$$ On the other hand, clearly $\mathsf{shift}(-4,\bullet)$ is not lossless on $\texttt{101011000}$, because we lose a $\texttt{1}$: $$\texttt{10101}\underbrace{\texttt{1000}}\rightarrow\texttt{10101}\rightarrow\texttt{10101}\underbrace{\texttt{0000}}$$
Now here’s the decision problem I’m thinking about:
Input: $n$ bitstrings $\langle x_0\rangle,\dots,\langle x_{n-1}\rangle$ of any length and not necessarily distinct.
Question: can we choose $n$ constants $c_0,\dots,c_{n-1}$ so that each $\mathsf{shift}(c_i,\bullet)$ is lossless on $\langle x_i\rangle $, and
$$\sum_{i=0}^{n-1} \mathsf{shift}(c_i,\langle x_i\rangle )=\texttt{111}\dots\texttt{1}\texttt{000}\dots\texttt{0}=\left(2^{y}-1\right)2^{z}$$ for some $y\geq 1$, $z\geq 0$? (Here the sum is the usual arithmetic sum: $\langle a\rangle + \langle b \rangle := \langle a+b\rangle$.)
In other words, we’re given a finite collection of bitstrings and asking if there’s some way of shifting them up or down (losslessly) so that their sum has exactly one unbroken interval of $\texttt{1}$s, followed by a possibly empty interval of $\texttt{0}$s. (This being theory, we’re assuming the register is infinite.)
What is the complexity of this problem with respect to the length of the input?
This problem feels NP-hard to me, since it’s a little bit like the subset-sum problem (but with a constraint on the sum rather than a single number we want to sum up to). It also seems a little similar to the $k$-SUM problem, which requires $n^{\Omega(k)}$ time unless for any constant $d$, $d$-SAT can be solved in time $2^{o(n)}$. A reduction from either of these problems would prove the bit-shifting problem is intractable (under reasonable assumptions). But of course, the big difference is that both of these problems involve finding a subset of the given set of numbers, and we're trying to use all $n$ bitstrings in our collection.
It’s a little more like a permutation problem, since permuting and concatenating the $n$ bitstrings is a special case of the class of candidate solutions. That might suggest looking for reductions from hard problems that involve permutations (e.g. the traveling salesman problem).
On the other side of things, I’ve had several ideas for polynomial-time algorithms since thinking of the problem. They’ve been dead-ends, or at least I’ve gotten stuck on them.
- I thought there might be some invariant that lets you swap the coefficients assigned to bitstrings in an arbitrary solution until they come in some agreeable order with respect to the original bitstrings. Then an algorithm could just take the bitstrings greedily in this order. It would be nice if we could factor each number $x_i$ into the canonical form $2^{a} x'_i$ for some $a\in\mathbb{N}$, where $x'_i$ is odd—then (WLOG) relabeling the bitstrings in order of these power-of-two coefficients. But I didn’t figure out any sort of swap move that could preserve the unbroken interval of $\texttt{1}$s.
- I had a couple ideas for dynamic programming tables, which I couldn’t even write down fully before realizing they weren’t going to work.
