Return to Answer

Suppose these bit strings were not vectors but representations of $n$-bit numbers in binary. Then the problem would be NP-complete by a reduction from the subset-sum problem. I will show how to make these vectors behave like they are binary numbers. What we need is to be able to do carries; that is, for every pair of adjacent coordinates, we need to be able to replace the vector ..02.. by ..10.. .

We reduce the problem of EQUAL SUM SUBSETS to this problem. EQUAL SUM SUBSETS is the problem of: given a set of $m$ integers, find two disjoint subsets which have the same sum. EQUAL SUM SUBSETS is known to be NP-complete.

Suppose these bit strings were not vectors but representations of $n$-bit numbers in binary. Then the problem would be NP-complete by a reduction from EQUAL SUM SUBSETS. I will show how to make these vectors behave like they are binary numbers. What we need is to be able to do carries; that is, for every pair of adjacent coordinates, we need to be able to replace the vector ..02.. by ..10.. .

OOPS: this answer doesn't quite work; see the comments. I know how to fix it, but it gets more complicated.

Because there can be at most $n$ carries in each place when adding $n$ numbers, we need to add $n$ triples of vectors for each coordinate in the original. You can do this by using a new pair of coordinates for each triple of vectors.

EDIT: My original proof had a bug. I now believe that it is fixed.

This construction works great if there is only one carry per position, but there could potentially be up to $n$ carries per position, and you need to make sure that your construction can handle up to $n$ carries, and that the different carries don't interfere with each other. For instance, if you added two different sets of three vectors for the same pair of adjacent positions (which is what I proposed in my original proof):

..01.. 01 00
..01.. 10 00
..10.. 11 00
..01.. 00 01
..01.. 00 10
..10.. 00 11

you have the problem that you get two different sets of vectors giving the same sum:

..01.. 01 00
..01.. 10 00
..10.. 00 11

=

..01.. 00 01
..01.. 00 10
..10.. 11 00

How to fix this? Add one set of vectors which lets you carry 1, one set which lets you carry 2, and one set for 4, 8, $\ldots$, 2$^{\lfloor \log n \rfloor}$. I'm not going to go work out the details of this construction right now, but it should be fairly straightforward. Since each number has a unique binary representation, this will let you carry any number up to $n$. For carrying 4, for example, you need find four vectors which have the same sum as two vectors, and for which this is the only linear relation between the two sets. For example, the set

..01.. 11000
..01.. 00100
..01.. 00010
..01.. 00001
..10.. 10001
..10.. 01110

works. You can easily check that the relation

11000
00100
00010
00001

=

10001
01110

is the only possible relation among these six vectors because the matrix formed by these six rows has rank 5.

Suppose these bit strings were not vectors but representations of $n$-bit numbers in binary. Then the problem would be NP-complete by a reduction from the subset-sum problem. I will show how to make these vectors behave like they are binary numbers. What we need is to be able to do carries; that is, for every pair of adjacent coordinates, we need to be able to replace the vector ..02.. by ..10.. .

How can we do that? We need a gadget that lets us do that. In particular, we need two subsets whose sums are ..02.. x and ..10.. x, where x is a bit string using new coordinates (i.e., coordinates which aren't any of the $n$ coordinates making up the binary representations), and where there is only one way to create two subsets with the same sum in the new bit positions corresponding to x.

This is fairly easy to do. For every pair of adjacent bit positions, add three vectors of the following form. Here the last two bits are coordinates which are non-zero only in these three vectors, and every bit not explicitly given below is 0.

..10.. 11
..01.. 10
..01.. 01

Let me do an example. We want to show how 5+3=8 works.

Here is 8 = 5 + 3 in binary:

1000

=

0101
0011

These bit strings give the same sum in binary, but not in vector addition.

Now, we have carries in the 1, 2, 4 places, so we need to add three sets of three vectors to the equation so as to perform these carries.

1000 00 00 00
0001 00 00 01
0001 00 00 10
0010 00 01 00
0010 00 10 00
0100 01 00 00
0100 10 00 00

=

0101 00 00 00
0011 00 00 00
0010 00 00 11
0100 00 11 00
1000 11 00 00

These sets now have the same sum in vector addition. The sums are:

1222 11 11 11

in both cases.

Because there can be at most $n$ carries in each place when adding $n$ numbers, we need to add $n$ triples of vectors for each coordinate in the original. You can do this by using a new pair of coordinates for each triple of vectors.

OOPS: this answer doesn't quite work; see the comments. I know how to fix it, but it gets more complicated.

Suppose these bit strings were not vectors but representations of $n$-bit numbers in binary. Then the problem would be NP-complete by a reduction from the subset-sum problem. I will show how to make these vectors behave like they are binary numbers. What we need is to be able to do carries; that is, for every pair of adjacent coordinates, we need to be able to replace the vector ..02.. by ..10.. .

How can we do that? We need a gadget that lets us do that. In particular, we need two subsets whose sums are ..02.. x and ..10.. x, where x is a bit string using new coordinates (i.e., coordinates which aren't any of the $n$ coordinates making up the binary representations), and where there is only one way to create two subsets with the same sum in the new bit positions corresponding to x.

This is fairly easy to do. For every pair of adjacent bit positions, add three vectors of the following form. Here the last two bits are coordinates which are non-zero only in these three vectors, and every bit not explicitly given below is 0.

..10.. 11
..01.. 10
..01.. 01

Let me do an example. We want to show how 5+3=8 works.

Here is 8 = 5 + 3 in binary:

1000

=

0101
0011

These bit strings give the same sum in binary, but not in vector addition.

Now, we have carries in the 1, 2, 4 places, so we need to add three sets of three vectors to the equation so as to perform these carries.

1000 00 00 00
0001 00 00 01
0001 00 00 10
0010 00 01 00
0010 00 10 00
0100 01 00 00
0100 10 00 00

=

0101 00 00 00
0011 00 00 00
0010 00 00 11
0100 00 11 00
1000 11 00 00

These sets now have the same sum in vector addition. The sums are:

1222 11 11 11

in both cases.

Because there can be at most $n$ carries in each place when adding $n$ numbers, we need to add $n$ triples of vectors for each coordinate in the original. You can do this by using a new pair of coordinates for each triple of vectors.