3
$\begingroup$

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.
$\endgroup$
1
  • $\begingroup$ I assume you care more about the theoretical worst-case asymptotic complexity, but if you care about practical solutions, I suggest specifying typical values of $n$ and the largest power of 2 dividing $x_i$. $\endgroup$
    – D.W.
    Nov 17, 2023 at 20:17

1 Answer 1

3
$\begingroup$

If I had to guess, I'd guess that the problem is hard, but I don't have a rigorous proof. I share below some musings on your problem, even though they don't lead to a clear answer to your question.


I suggest that a first question for you to consider is to see if you can prove that the problem is in NP. This is not trivial, as $c_i,z$ can be arbitrarily large, so you need to prove that if there exists a solution, then there exists a polynomial-sized solution (i.e., where the length of $c_i,z$ are polynomial). I don't immediately have a proof of that.

Setting that aside, let's move on to the hardness of this problem.


Without loss of generality, your problem is equivalent to the following:

Powered Subset-sum:

Input: $w_1,\dots,w_n \in \mathbb{N}$

Question: does there exist $e_1,\dots,e_n \in \mathbb{N}$ and $y,z \in \mathbb{N}$ such that

$$\sum_{i=1}^{n} 2^{e_i} w_i = (2^y-1)2^z$$

Why is this equivalent? Given an instance $x_1,\dots,x_n$ to your problem, we can set $w_i = x_i/2^{p_i}$, where $2^{p_i}$ is the largest power of 2 that divides $x_i$; then any solution to this problem can be transferred to a solution to your problem by setting $c_i=e_i-p_i$; and vice versa.


Consider this variant problem:

Powered Variant:

Input: $w_1,\dots,w_n,y,z \in \mathbb{N}$

Question: does there exist $e_1,\dots,e_n \in \mathbb{N}$ such that

$$\sum_{i=1}^{n} 2^{e_i} w_i = (2^y-1)2^z$$

This differs from Powered Subset-sum by forcing a particular value for $y,z$ rather than allowing the algorithm to choose them freely.


Now I suspect that Powered Variant is likely hard. Why? It is very closely related to the subset-sum problem. The two differences are:

  • In the subset-sum problem, the target $t$ is part of the input, and can be arbitrary. In Powered Variant, $t$ must take the form $t=(2^y-1)2^z$.

    How does this affect the complexity? Hard to say. Personally, I would find it surprising if it is easier to solve the subset-sum problem for this particular type of target than others.

  • In the subset-sum problem, we can either include $w_i$ or exclude it. This corresponds to adding the extra restriction that $0 \le e_i \le 1$. In Powered Variant, we only have the restriction $0 \le e_i$.

    How does this affect the complexity? Hard to say. I would find it surprising if this extra degree of freedom is enough to make the problem easy. In particular, consider instances where all $w_i$'s are large and of a similar size. Then I expect that solutions with large values of $e_i$ are "sparser".

However, anything is possible. This does not prove that Powered Variant is NP-hard.


Back to Powered Subset-sum. How might its hardness compare to that of Powered Variant? It's hard to know. But the resemblance makes me suspect that Powered Subset-sum has a good chance of being hard. It's hard to know for sure, though, as there is the remote possibility that using very large values of $e_i,z$ might provide extra degrees of freedom that make the problem easier.


None of this is a proof, or even super convincing. Perhaps it gives some suggestive ideas. Perhaps you could take a look at standard proofs of hardness for the subset sum problem (by reduction from some other NP-complete problem), and see if any of them can be adjusted to work with your problem.

$\endgroup$
3
  • $\begingroup$ I do think the variants you propose are useful, but I don’t understand how restricting $e_i$ to $0\leq e_i\leq 1$ would correspond to including or excluding the corresponding $w_i$, since $e_i$ is the exponent of $2$—so setting it to $0$ just gives a coefficient of $1$, and setting it to $1$ gives a coefficient of $2$. Is that right? $\endgroup$ Nov 24, 2023 at 1:08
  • 2
    $\begingroup$ @SophieWeigle, when $e_i \in \{0,1\}$, then $2^{e_i}=1 + e_i$, so $\sum_i 2^{e_i} \cdot w_i = \sum_i w_i + \sum_i e_i \cdot w_i$. Here $\sum_i w_i$ is a constant (which you can add/subtract from the target, to get a new target), and $\sum_i e_i \cdot w_i$ is from the traditional subset-sum problem (either including or excluding the $w_i$). $\endgroup$
    – D.W.
    Nov 24, 2023 at 22:11
  • $\begingroup$ I forgot to thank you for the clarification, but thank you for the clarification! $\endgroup$ Jan 23 at 23:29

Your Answer

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

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