Two bits are enough for a “hard” sum

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.

3 thoughts on “Two bits are enough for a “hard” sum

Leave a Reply

Your email address will not be published. Required fields are marked *