Take the 2-minute tour ×
Computer Science Stack Exchange is a question and answer site for students, researchers and practitioners of computer science. It's 100% free, no registration required.

Is this variant of the subset sum problem easy/known?

Given an integer $m$, and a set of positive 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$ ?

Is it in $\sf{P}$? Is it still $\sf{NP}$-complete?

And if every $x_i$ has at most $k=3$ bits set to $1$? For $k=1$ the problem is trivial.

share|improve this question

2 Answers 2

up vote 8 down vote accepted

It is still $\sf{NP}$-complete, even for $k=2$. Given an instance of subset sum, we can transform it in to this variant by splitting up the numbers and adding some extra bits.

First, the sum of all numbers in the problem will be less than $2^m$ for some value of $m$.

Now, let's take a number $n$ from the original problem which has $k$ bits set. We will split this number in to $k$ numbers with exactly 2 bits set such that the sum of those numbers is $n+2^{k+m}$. We can do this recursively, by finding $\lceil{k}\rceil$ numbers that sum up to the first $\lceil{k}\rceil$ bits plus $2^{k+m-1}$ and $\lfloor{k}\rfloor$ numbers that sum up to the last $\lfloor{k}\rfloor$ bits plus $2^{k+m-1}$.

In addition to that number we will also add the number $2^{k+m}$ to the problem. A solution must either contain this number or all of the $k$ numbers constructed previously. If the original target value was $t$ the new target value will be $t+2^{k+m}$.

If the original problem had more than one number, we can repeat this process taking $k+m+1$ for the new value of $m$.

There are only two ways the bit at position $k+m$ can be set: the answer can contain the number $2^{k+m}$ or all of the $k$ numbers that sum up to $n+2^{k+m}$. So we have reduced subset sum to your subset sum variant.

As an example, let's take ${\{2,3,5\}}$ with target value $7$. This problem could be encoded as the subset sum variant presented here by taking the following binary numbers:

2 gets mapped to $0100\ 1$ and $0000\ 1$. (Using the extra bit is not strictly necessary here.)

3 gets mapped to $1000\ 00\ 1, 0100\ 00\ 1$ and $0000\ 00\ 01$

5 gets mapped to $1000\ 00\ 000\ 1, 0010\ 00\ 000\ 1$ and $0000\ 00\ 000\ 01$.

The new target value would become $1110\ 10\ 010\ 01$.

If the original problem is represented with $n$ bits, then the transformed problem has at most $O(n^4)$ bits. The original problem will have at most $O(n)$ numbers each with at most $O(n)$ bits, so the sum of all of them is also O(n). The transformed problem will have $O(n^2)$ numbers (since each $n$-bit number is split in to $n+1$ $2$-bit numbers, with their length being at most $O(n^2)$ since we use $n$ additional bits for each number. So the total size of the transformed problem is $O(n^4)$ bits.

share|improve this answer
    
are you sure that the encoding doesn't lead to an exponential size of the working tape? –  Vor Jan 17 '13 at 22:00
    
No, I think the transformed problem is quartic in size. If the input has n bits, then there are at most n numbers each with n bits set. So there will be O(n^2) numbers in the transformed problem (since a k-bit number is split in to k+1 numbers). Each number is (2n) bits long to accommodate the maximal sum plus n bits for each of the n numbers in the original problem. So each number will have O(2n+n^2) bits, for a total of O(n^4) bits. –  Tom van der Zanden Jan 17 '13 at 22:11
    
@TomvaderZanden: I added a picture of your reduction in the question; see if I interpreted it correctly –  Vor Jan 17 '13 at 22:51
    
@TomvaderZanden: today I look at your reduction again, but it is unclear how from an arbitrary number $n$ with $k$ bits set you can split it into $k$ 2-bit numbers where the "highest" part sums to $2^k$. Suppose you have a number $n$ with $k=13$ bits set; you need 13 2-bit numbers, but 13 is 1101 and you cannot "cover" it with a two bit number (your example works because for 3 and 5 k=2). I think that this can be easily fixed if you use a different high bit for each of the $k$ 2-bit numbers; they will sum to 01111...1, then you add a dummy 0000...1 that will allow the sum to be $2^k$. –  Vor Jan 18 '13 at 15:04
    
It is a bit vague, but it is certainly possible using an "inductive" procedure. You don't actually need $k$ bits, you only need $ceil(\log k)$. If you want to find 13 1-bit numbers that sum up to $2^4$, then you need to find 6 numbers that sum up to $2^3$ and 7 that also sum up to $2^3$. We can take $10*2^0+3*2^1$ which indeed sums up to $2^4$. –  Tom van der Zanden Jan 19 '13 at 11:52

This is information extracted from question by Vor.

For $k \geq 3$ the problem remains NP-complete. I found a quick reduction from monotone X-SAT (see the schema of the reduction here).

The problem remains NP-complete even if $k = 2$, see Tom's answer for details. Here is a small representation of his reduction from SUBSET SUM:

enter image description here

share|improve this answer

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

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