<p>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.</p>
<hr />
<p>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 <span class="math-container">$c_i,z$</span> 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 <span class="math-container">$c_i,z$</span> are polynomial).  I don't immediately have a proof of that.</p>
<p>Setting that aside, let's move on to the hardness of this problem.</p>
<hr />
<p>Without loss of generality, your problem is equivalent to the following:</p>
<blockquote>
<p>Powered Subset-sum:</p>
<p>Input: <span class="math-container">$w_1,\dots,w_n \in \mathbb{N}$</span></p>
<p>Question: does there exist <span class="math-container">$e_1,\dots,e_n \in \mathbb{N}$</span> and <span class="math-container">$y,z \in \mathbb{N}$</span> such that</p>
<p><span class="math-container">$$\sum_{i=1}^{n} 2^{e_i} w_i = (2^y-1)2^z$$</span></p>
</blockquote>
<p>Why is this equivalent?  Given an instance <span class="math-container">$x_1,\dots,x_n$</span> to your problem, we can set <span class="math-container">$w_i = x_i/2^{p_i}$</span>, where <span class="math-container">$2^{p_i}$</span> is the largest power of 2 that divides <span class="math-container">$x_i$</span>; then any solution to this problem can be transferred to a solution to your problem by setting <span class="math-container">$c_i=e_i-p_i$</span>; and vice versa.</p>
<hr />
<p>Consider this variant problem:</p>
<blockquote>
<p>Powered Variant:</p>
<p>Input: <span class="math-container">$w_1,\dots,w_n,y,z \in \mathbb{N}$</span></p>
<p>Question: does there exist <span class="math-container">$e_1,\dots,e_n \in \mathbb{N}$</span> such that</p>
<p><span class="math-container">$$\sum_{i=1}^{n} 2^{e_i} w_i = (2^y-1)2^z$$</span></p>
</blockquote>
<p>This differs from Powered Subset-sum by forcing a particular value for <span class="math-container">$y,z$</span> rather than allowing the algorithm to choose them freely.</p>
<hr />
<p>Now I suspect that Powered Variant is likely hard.  Why?  It is very closely related to the subset-sum problem.  The two differences are:</p>
<ul>
<li><p>In the subset-sum problem, the target <span class="math-container">$t$</span> is part of the input, and can be arbitrary.  In Powered Variant, <span class="math-container">$t$</span> must take the form <span class="math-container">$t=(2^y-1)2^z$</span>.</p>
<p>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.</p>
</li>
<li><p>In the subset-sum problem, we can either include <span class="math-container">$w_i$</span> or exclude it.  This corresponds to adding the extra restriction that <span class="math-container">$0 \le e_i \le 1$</span>.  In Powered Variant, we only have the restriction <span class="math-container">$0 \le e_i$</span>.</p>
<p>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 <span class="math-container">$w_i$</span>'s are large and of a similar size.  Then I expect that solutions with large values of <span class="math-container">$e_i$</span> are &quot;sparser&quot;.</p>
</li>
</ul>
<p>However, anything is possible.  This does not prove that Powered Variant is NP-hard.</p>
<hr />
<p>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 <span class="math-container">$e_i,z$</span> might provide extra degrees of freedom that make the problem easier.</p>
<hr />
<p>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.</p>

CC BY-SA 4.0
2023-11-24T01:08:46.253Z
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?
wobtax
CC BY-SA 4.0
2023-11-24T22:11:27.263Z
@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$).
D.W.
CC BY-SA 4.0
2024-01-23T23:29:53.140Z
I forgot to thank you for the clarification, but thank you for the clarification!
wobtax
CC BY-SA 4.0
2023-11-17T20:56:34.127Z
2023-11-17T20:56:34.127Z
D.W.
<p>I’ve been wondering about the computational complexity of a problem that involves bit shifting.</p>
<p>Let me define some notation before I present the problem.
If <span class="math-container">$\langle{b}\rangle$</span> is a bitstring representing a natural number <span class="math-container">$b$</span>, let <span class="math-container">$\mathsf{shift}(c,\langle{b}\rangle):=\langle\lfloor b \cdot 2^{c}\rfloor\rangle$</span> for a constant <span class="math-container">$c\in\mathbb{Z}$</span>. In other words, the function <span class="math-container">$\mathsf{shift}(c,\bullet)$</span> performs a bit shift of <span class="math-container">$c$</span> steps upward (or <span class="math-container">$-c$</span> steps downward, if <span class="math-container">$c$</span> is negative).</p>
<p>Let’s say a bit shift function <span class="math-container">$\mathsf{shift}(c, \bullet)$</span> is <em>lossless</em> on the bitstring <span class="math-container">$\langle x\rangle$</span> if <span class="math-container">$\mathsf{shift}(-c,\mathsf{shift}(c,x))=\langle x\rangle$</span>. For example, <span class="math-container">$\mathsf{shift}(-3,\bullet)$</span> is lossless on <span class="math-container">$\texttt{101011000}$</span>:
<span class="math-container">$$\texttt{101011}\underbrace{\texttt{000}}\rightarrow\texttt{101011}\rightarrow\texttt{101011}\underbrace{\texttt{000}}$$</span>
On the other hand, clearly <span class="math-container">$\mathsf{shift}(-4,\bullet)$</span> is not lossless on <span class="math-container">$\texttt{101011000}$</span>, because we lose a <span class="math-container">$\texttt{1}$</span>:
<span class="math-container">$$\texttt{10101}\underbrace{\texttt{1000}}\rightarrow\texttt{10101}\rightarrow\texttt{10101}\underbrace{\texttt{0000}}$$</span></p>
<p>Now here’s the decision problem I’m thinking about:</p>
<hr />
<p><strong>Input:</strong> <span class="math-container">$n$</span> bitstrings <span class="math-container">$\langle x_0\rangle,\dots,\langle x_{n-1}\rangle$</span> of any length and not necessarily distinct.</p>
<p><strong>Question:</strong> can we choose <span class="math-container">$n$</span> constants <span class="math-container">$c_0,\dots,c_{n-1}$</span> so that each <span class="math-container">$\mathsf{shift}(c_i,\bullet)$</span> is lossless on <span class="math-container">$\langle x_i\rangle $</span>, and</p>
<p><span class="math-container">$$\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}$$</span>
for some <span class="math-container">$y\geq 1$</span>, <span class="math-container">$z\geq 0$</span>? (Here the sum is the usual arithmetic sum: <span class="math-container">$\langle a\rangle + \langle b \rangle := \langle a+b\rangle$</span>.)</p>
<hr />
<p>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 <em>exactly one</em> unbroken interval of <span class="math-container">$\texttt{1}$</span>s, followed by a possibly empty interval of <span class="math-container">$\texttt{0}$</span>s. (This being theory, we’re assuming the register is infinite.)</p>
<p><strong>What is the complexity of this problem</strong> with respect to the length of the input?</p>
<p>This problem feels NP-hard to me, since it’s a <em>little</em> bit like the subset-sum problem (but with a <em>constraint</em> on the sum rather than a single number we want to sum up to). It also seems a little similar to the <a href="https://cs.stackexchange.com/questions/2973/generalised-3sum-k-sum-problem"><span class="math-container">$k$</span>-SUM problem</a>, which requires <span class="math-container">$n^{\Omega(k)}$</span> time unless for any constant <span class="math-container">$d$</span>, <span class="math-container">$d$</span>-SAT can be solved in time <span class="math-container">$2^{o(n)}$</span>. 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 <em>subset</em> of the given set of numbers, and we're trying to use all <span class="math-container">$n$</span> bitstrings in our collection.</p>
<p>It’s a little more like a <em>permutation</em> problem, since permuting and concatenating the <span class="math-container">$n$</span> 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).</p>
<p>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.</p>
<ul>
<li>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 <span class="math-container">$x_i$</span> into the canonical form <span class="math-container">$2^{a} x'_i$</span> for some <span class="math-container">$a\in\mathbb{N}$</span>, where <span class="math-container">$x'_i$</span> 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 <span class="math-container">$\texttt{1}$</span>s.</li>
<li>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.</li>
</ul>

CC BY-SA 4.0
2023-11-17T20:17:25.307Z
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$.
D.W.
<np-hardness><complexity><arithmetic-circuits><permutations>
What’s the complexity of this decision problem with bit shifting?
wobtax
# What’s the complexity of this decision problem with bit shifting?

(Asked by: username_0 on 2023-11-16)

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](https://cs.stackexchange.com/questions/2973/generalised-3sum-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.

**Tags:** np-hardness, complexity, arithmetic-circuits, permutations

> **Comments:**
> **username_1**: 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$.  

---

## 1 answers

### Answer by username_1 on 2023-11-17. Score: 3

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.

> **Comments:**
> **username_0**: 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?  
> **username_1**: @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$).  
> **username_0**: I forgot to thank you for the clarification, but thank you for the clarification!  

---

