27
$\begingroup$

Given an $m$ by $n$ binary matrix $M$ (entries are $0$ or $1$), the problem is to determine if there exists two binary vectors $v_1 \ne v_2$ such that $Mv_1 = Mv_2$ (all operations performed over $\mathbb{Z}$). Is this problem NP-hard?

It is clearly in NP as you can give two vectors as witnesses.


Equivalently: Given $M$, is there a non-zero vector $v\in \{-1,0,1\}^n$ such that $Mv=0$?

Equivalently: Given $n$ vectors $X=\{x_1,\dots,x_n\}$ over $\{0,1\}^m$, are there two different subsets $A,B \subseteq X$ such that $\sum_{x \in A} x = \sum_{x \in B} x$?

$\endgroup$
  • $\begingroup$ Unless I misunderstand the question, is this not equivalent to determining if there is a non-zero $v$ such that $Mv = 0$? And isn't this solved by determining the rank of $M$? $\endgroup$ – mhum Dec 20 '13 at 21:36
  • 8
    $\begingroup$ @mhum no, it's equivalent to determining if there is a nonzero $v \in \{-1, 0, 1\}^n$ such that $Mv = 0$. $\endgroup$ – Sasho Nikolov Dec 20 '13 at 21:38
  • $\begingroup$ Ah. I missed that $v_i$ also had to be binary. My mistake. $\endgroup$ – mhum Dec 20 '13 at 21:44
  • 2
    $\begingroup$ Seems like the feasibility problem for 0/1-Integer Programming. Are operations over $\mathbb{Z}$ or over $\mathbb{Z_2}$? $\endgroup$ – Kaveh Dec 20 '13 at 21:45
  • 3
    $\begingroup$ Reformulation of the problem: Given $n$ vectors $X = \{ x_1,\dots,x_n \}$ over $\{ 0,1 \}^m$. Are there two different subsets $A,B \subseteq {X}$ such that $\sum_{x \in A} x = \sum_{x \in B} x$? I'd think that it is more likely to be NP-hard if the sums are not taken modulo two, that is operations are over $\mathbb{Z}$ $\endgroup$ – John D. Dec 20 '13 at 22:06
7
$\begingroup$

I use the user17410 equivalent formulation:

Input: $n$ vectors $X = \{ x_1, \dots, x_m \}$ over $\{0,1\}^n$, $n$ is part of the input
Question: Are there two different subsets $A,B \subseteq X$ such that $$\sum_{x \in A} x = \sum_{x \in B} x$$

The hardness proof involve many intermediate reductions that follow the same "chain" used to prove the hardness of the standard EQUAL SUBSET SUM problem:

X3C $\leq$ SUBSET SUM $\leq$ PARTITION $\leq$ EVEN-ODD PARTITION $\leq$ EQUAL SUBSET SUM

(I'm still checking it so it may be wrong :)

STEP 1

The following problem (0-1 VECTOR SUBSET SUM) is NP-complete: given $X = \{ x_1, \dots, x_m \}$, $x_i$ vectors over $\{0,1\}^n$ and a target sum vector $t$, decide if there is $A \subseteq X$ such that $$\sum_{x \in A} x = t$$ Proof: Direct reduction from EXACT COVER BY 3-SETS (X3C): given a set of $n$ elements $Y = \{y_1,...,y_n\}$ and a collection $C$ of $m$ three elements subsets $C = \{C_1,...,C_m\}$ we build the corresponding 0-1 VECTOR SUM instance setting $x_i[j] = 1$ if and only if element $j$ is included in $C_i$; $t = [1,1,...1]$.

STEP 2 Finding two equal sum subsets $A,B$ among $m$ 0-1 vectors over $\{0,1\}^n$, is equivalent to finding two equal sum subsets $A,B$ of vectors with element of bounded size $x_1 ... x_m$ where $max\{x_i\} = O((mn)^k)$ for fixed $k$.

For example the set of vectors:

x1 2 1 0 1
x2 1 2 3 1

Is equvalent to the 0-1 vectors:

x1  1 1 0 1   1 0   0 0 0
    1 0 0 0   0 1   0 0 0 
    0 0 0 0   1 1   0 0 0 
              ^ ^
                +-- 0 elsewhere

x2  1 1 1 1   0 0   1 0 0
    0 1 1 0   0 0   0 1 0
    0 0 1 0   0 0   0 0 1
    0 0 0 0   0 0   1 1 1
                    ^ ^ ^
                      +-- 0 elsewhere

Informally the 0-1 vectors are grouped (if you select one vector of the x2 group and add it to subset $A$, then you are forced to include in $A$ the other two and put the last in subset $B$) and the sums are done in unary (this is the reason why the corresponding non binary vectors must contain elements that are polynomially bounded with respect to $mn$).

So the following problem is NP-complete.

STEP 3

The following problem (0-1 VECTOR PARTITION) is NP-complete: given $B = \{ x_1, \dots, x_m \}$, $x_i$ vectors over $\{0,1\}^n$ decide if $X$ can be partitioned in two subsets $B_1, B_2$ such that $$\sum_{x \in B_1} x = \sum_{x \in B_2} x$$

Proof: Reduction from 0-1 VECTOR SUM: given $X = \{ x_1, \dots, x_m \}$ and the target sum vector $t$; let $S = \sum x_i$, we add to $X$ the following vectors: $b' = -t + 2S$ and $b'' = t + S\;$: $B = X \cup \{b',b''\}$.

($\Rightarrow$) Suppose that there exists $A \subseteq X$ such that $\sum_{x \in A} x= t$; we set $B_1 = A \cup \{b'\}$ and $B_2 =B \setminus B_1 = X \setminus \{A\} \cup \{b''\}$; we have $$\sum_{x \in B_1} = b'+\sum_{x \in A} x = t - t + S = 2S$$ $$\sum_{x \in B_2} = b'' + \sum_{x \in X\setminus A} x = b'' + S - \sum_{x \in A} x=2S$$

($\Leftarrow$) Suppose that $B_1$ and $B_2$ have equal sum. $b', b''$ cannot both belong to the same set (otherwise their sum is $\geq 3S$ and cannot be "balanced" by the elements in the other set). Suppose that $b' = -t + 2S \in B_1$; we have:

$$-t +2S+ \sum_{x \in B_1 \setminus\{b'\}} x = t + S + \sum_{x \in B_2 \setminus\{b''\}} x$$

Hence we must have $\sum_{x \in B_1 \setminus\{b'\}} x = t$ and $B_1 \setminus\{b'\}$ is a valid solution for the 0-1 VECTOR SUM.

We only allow 0-1 vectors in the set $B$, so vectors $b', b''$ must be "represented in unary" as shown in STEP 2.

STEP 3

The problem is still NP-complete if the vectors are numbered from $x_1,...,x_2n$ and the two subsets $X_1,X_2$ must have equal size and we require that $X_1$ contains exactly one of $x_{2i-1},x_{2i}$ for $1 \leq i \leq n$ (so, by the equal size constraint, the other element of the pair must be included in $X_2$) (0-1 VECTOR EVEN-ODD PARTITION).

Proof:: The reduction is from 0-1 VECTOR PARTITION and is similar to the reduction from PARTITION to EVEN-ODD PARTITION. If $X = \{x_1,...,x_m\}$ are $m$ vectors over $\{0,1\}^n$ replace each vector with two vectors over $\{0,1\}^{2n+2m}$:

       1   2       n
 --------------------
 x_i  b_1 b_2 ... b_n

 becomes:

           1 2 ... 2i ... 2m
  --------------------------
  x'_2i-1  0 0 ...  1 ...  0  b_1 b_2 ... b_n   0   0  ...  0  
  x'_2i    0 0 ...  1 ...  0   0   0  ...  0   b_1 b_2 ... b_n 

Due to the $2i$ element, the vectors $x'_{2i-1}$ and $x'_{2i}$ cannot be contained in the same subset; and a valid solution to the 0-1 VECTOR EVEN-ODD PARTITION correspond to a valid solution of the original 0-1 VECTOR PARTITION (just pick elements 2m+1..2m+n of each vector of the solution discarding vectors that contain all zeros in those positions).

STEP 4

0-1 VECTOR EQUAL SUBSET SUM (the problem in the question) is NP-complete: reduction from 0-1 VECTOR EVEN-ODD PARTITION similar to the reduction from EVEN-ODD PARTITION to EQUAL SUM SUBSET, as proved in Gerhard J. Woeginger, Zhongliang Yu, On the equal-subset-sum problem: given an ordered set $A = \{x_1,...,x_{2m}\}$ of $2m$ vectors over $\{0,1\}^n$, we build a set $Y$ of $3m$ vectors over $\{0,1\}^{2m+n}$.

For every vector $x_{2i-1}, 1 \leq i \leq m$ we build a vector $y_{2i-1}$ over $\{0,1\}^{2m+n}$ in this way:

  1 2 ... i i+1 ... m  m+1 m+2 ... m+i ... 2m  2m+1 ... 2m+n
  ------------------------------------------------------
  0 0 ... 2  0  ... 0   0   0       1       0  x_{2i-1}

For every vector $x_{2i}, 1 \leq i \leq m-1$ we build a vector $y_{2i}$ over $\{0,1\}^{2m+n}$ in this way:

  1 2 ... i i+1 ... m  m+1 m+2 ... m+i ... 2m  2m+1 ... 2m+n
  ------------------------------------------------------
  0 0 ... 0  2  ... 0   0   0       1       0  x_{2i}

We map element $x_{2m}$ to

  1 2 ...       ... m  m+1 m+2 ...  . 2m  2m+1 ... 2m+n
  ------------------------------------------------------
  2 0 ...       ... 0   0   0          1  x_{2m}

Finally we add $m$ dummy elements:

  1 2 ...       ... m  m+1 m+2 ...  ... 2m  2m+1 ... 2m+n
  ------------------------------------------------------
  4 0 ...       ... 0   0   0            0  0    ... 0
  0 4 ...       ... 0   0   0            0  0    ... 0
  ...
  0 0 ...       ... 4   0   0            0  0    ... 0

Note again that vectors containing values $> 1$ can be represented in "unary" using a group of 0-1 vectors like showed in STEP 2.

$Y$ has two disjoint $Y_1,Y_2$ subsets having equal sum if and only if $X$ has an even-odd partition.

$\endgroup$
  • $\begingroup$ what you call 0-1 vector partition is equivalent to the problem of determining if a set system has discrepancy 0. this is NP hard, since it captures e.g. the 2-2-set-splitting problem, see thm 9 in this paper by guruswami cs.cmu.edu/~venkatg/pubs/papers/ss-jl.ps; my paper has a bit more on the hardness of discrepancy paul.rutgers.edu/~anikolov/Files/charikarM.pdf $\endgroup$ – Sasho Nikolov Dec 26 '13 at 0:41
  • $\begingroup$ also I believe you mis-state the even-odd partition problem. if no two consecutive vectors can be in the same set the problem is trivial. i believe you mean that $|X_i \cap \{x_{2j-1}, x_{2j}\}| = 1$ is required for all $i \in \{1, 2\}$ and $1 \leq j \leq m$ $\endgroup$ – Sasho Nikolov Dec 26 '13 at 7:46
  • $\begingroup$ @SashoNikolov: yes, I mean that for every pair $(x_{2i-1},x_{2i})$ (and in the proof $(x'_{2i-1}, x'_{2i})$) exactly one is included in $X_1$; I'll edit the answer $\endgroup$ – Marzio De Biasi Dec 26 '13 at 8:36
8
$\begingroup$

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

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.. .

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.

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.

$\endgroup$
  • $\begingroup$ A clarification, you say "Now, we have carries in the 1, 2, 4 places"; but in the problem we don't know which vectors are selected so we must add the carry gadget to every adjacent bit position? And in the first list of the example there are 7 vectors, is it correct? $\endgroup$ – Marzio De Biasi Dec 25 '13 at 18:41
  • $\begingroup$ Suppose have a solution for the subset sum problem. That is: we have 3+5=8. Now, we can look at the addition in this witness and find out where the carries are. This gives us the solution for the vector addition problem. One problem has a solution if and only if the other does. $\endgroup$ – Peter Shor Dec 25 '13 at 18:44
  • $\begingroup$ But how the reduction works for example if the instance of the subset sum is $2,3,5,7$ and target sum $8$ (what is the corresponding vector instance)? $\endgroup$ – Marzio De Biasi Dec 25 '13 at 18:46
  • $\begingroup$ P.S. I also found a proof that the problem is NP-complete, but it is much longer than yours, so I'm trying to understand it ... simpler is better :-) $\endgroup$ – Marzio De Biasi Dec 25 '13 at 18:47
  • $\begingroup$ This means that for the second problem, we have to add the carry gadget to every adjacent bit position. In fact, since we might have $n-1$ carries in that position, we have to add $n-1$ copies of the carry gadget to that bit position. And I just realized that doesn't work — we have to be cleverer. I know how to do it, but I'll have to revise the answer. $\endgroup$ – Peter Shor Dec 25 '13 at 18:47
3
$\begingroup$

This doesn't answer the question but might contain some helpful observations. I didn't want to put it as a comment because I find long, fragmented comments bothersome to read

The reformulation of the problem as stated in my comment to the question:

Input: $n$ vectors $X = \{ x_1, \dots, x_n \}$ over $\{0,1\}^m$, $m$ is part of the input

Question: Are there two different subsets $A,B \subseteq X$ such that $$\sum_{x \in A} x = \sum_{x \in B} x$$

Maybe I should note that one should regard $X,A,B$ as multisets(the vectors must not be unique) and the sums are over $\mathbb{N}$.

I propose to call this problem 2SUBSET-BINARY-VECTOR-SUM due to the fact that we are looking for 2 subsets of binary vectors.

Some observations:

  • If $X$ contains one vector multiple times the answer becomes trivial. Let $x_i,x_j \in X$ and $x_i = x_j$. Then $A = \{x_i\}, B = \{x_j\}$ works as witness.

  • If one of the vectors in $X$ contains only 0's it is trivial. Let $0 \in X$ be that vector. Then for every $A \subseteq X \setminus \{ 0 \}$ it follows $B = A \cup \{ 0 \}$ is a witness.

  • Assume there exists a witness such that $A \subset B$. This implies that every vector that is in $B$ but not in $A$ must consist of zeroes only.

  • To subsume the above two points: a witness $A,B$ with $A \subset B$ exists iff at least one of the vectors in $X$ contains only zeroes

  • Assume there exists a witness $A,B$ such that $A \cap B \neq \emptyset$. You can remove the common elements in both sets and still have a correct witness.

These points essentialy mean that you are looking for a partition of $X$ into two sets($A \cup B = X$) or three sets. The third set represents the vectors which weren't choosen for either $A$ or $B$. Let $S(n,k)$ be the Stirling numbers of the second kind - the number of ways to partition a set of $n$ objects into $k$ non-empty partitions. Then there are $S(n,3)+S(n,2)$ possible solutions, so brute force isn't feasible here.

If you allow the vectors to be over $\mathbb{N}^m$ (2SUBSET-VECTOR-SUM), then we can try to reduce UNIQUE-PARTITION to this problem. Let $m=1$ and simply pass the instance of UNIQUE-PARTITION(if it contains 0, remove it first to avoid trivial solutions). However, this doesn't work since possible solutions $A,B$ don't necessarily contain all input elements:

Consider $\{1,2,3,5\}$. This isn't in UNIQUE-PARTITION but $A=\{1,2\} , B = \{3\}$ in 2SUBSET-VECTOR-SUM. Maybe using $m>1$ we can use the additional vector entries to force $A,B$ to partition the input.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy