On Jan 17 I asked the following question on cs.stackexchange.com:

What is the complexity of the following variant of the SUBSET-SUM decision problem?

2-BIT SUBSET SUM: Given an integer $m \geq 0$, and a set of nonnegative integers $A = \{x_1, x_2, …, x_n\}$ such that every $x_i$ has at most $k=2$ bits set to $1$ ($x_i = 2^{b_{i_1}}+2^{b_{i_2}},\;\; b_{i_1},b_{i_2}\geq 0$); is there a subset $A’ \subseteq A$ such that the sum of its elements is equal to $m$ ?

(see the original question and answer on cs.stackexchange)

The problem is trivially solvable in polynomial time if $k=1$ and I quickly found a reduction from monotone X-SAT if $k=3$; but Tom van der Zanden found an easy reduction from SUBSET-SUM even if $k=2$. Here it is a sketch of the polynomial time reduction.

The main idea is that an integer $x$ of the original SUBSET-SUM problem having $k > 2$ bits set to 1, can be converted to $k\;$ 2-bit integers (here "2-bit integer" means *having at most 2 bits equal to 1*) $y_1,…,y_k$ such that $y_1+y_2+…+y_k = 2^{(k-1)+t} + x$ where $t$ is a large enough integer that will be used to keep the sum of the high bits of the $y$s distinct

Suppose that $b_1, b_2, …, b_k$ are the positions of the bits that are set to 1 in the integer $x$, then we set $y_1 = 2^{b_1} + 2^{t}$, $y_2 = 2^{b_2} + 2^{t}$ and for $2 < j \leq k$: $y_j = 2^{b_j} + 2^{t+j-2}$. For example if $x = 53 = 110101_2$:

...t...543210 << bit position x: ...110101 (k = 4) y1: 1...000001 y2: 1...000100 y3: 10...010000 y4: 100...100000 sum: 1000...110101 = 2^{(k-1)+t} + x

Now if we add an extra integer $z = 2^{(k-1)+t}$ and we modify the target of the original subset sum problem: $m' = m + 2^{(k-1)+t}$ then a valid solution in the corresponding 2-BIT SUBSET SUM problem *must* contain $z$ or (exclusive) *all* the $y_j$:

x: ...110101 (k = 4) y1: 1...000001 y2: 1...000100 y3: 10...010000 y4: 100...100000 sum: 01000...110101 = 2^{(k-1)+t} + x z: 01000...000000 = 2^{(k-1)+t} m': 01000...[ m ] = 2^{(k-1)+t} + m ^ this new bit in the target sum force a valid solution to contain z or (exclusive) ALL the y1...y4 above

The whole reduction from SUBSET SUM problem to 2-BIT SUBSET SUM problem can be done in the following way:

given an instance of the SUBSET SUM problem, i.e. an integer $m \geq 0$ and a set of $n$ nonnegative integers $A = x_1,...,x_n$ (all in binary format); start with $t$ equal to $\lceil \log_2(\sum_i x_i) \rceil + 1$, $A' = \emptyset$, $m' = m$. For each $x_i \in A$: if $x_i$ has $k=2$ or fewer bits equal to 1 add it to $A'$, otherwise if it has more than 2 bits equal to 1, calulate the corresponding integers $y_j$ and $z$ and set $A' = A' \cup \{ y_1,...,y_k\} \cup \{ z \}$ and $m' = m' + 2^{(k-1)+y}$, finally increase $t = t + k + 1$.

The resulting 2-BIT SUBSET SUM problem with target sum $m'$ and the set of 2-bit integers $A'$ has a solution if and only if the original SUBSET SUM problem has a solution.

**Conclusion:** the SUBSET SUM problem remains $\sf{NP}$-complete even if we restrict the integers of the given set to have at most 2 bits equal to 1.

Is a similar claim true for subset product problem?

Nice question. I don’t see a quick similar proof; I’ll think about it.

Could you show your reduction from X-SAT if k=3?