<p>I think I got a reduction by combining the reduction from @Chandra and idea from other reductions to avoid passing by ODD EVEN PARTITION.</p>
<p>As in Chandra's reduction, we reduce from restricted X3C and build the same vectors <span class="math-container">$x_1, ..., x_k$</span> of size <span class="math-container">$3q$</span>. We add <span class="math-container">$k-1$</span> new vectors <span class="math-container">$y_1, ..., y_{k-1}$</span> of zeros. For all <span class="math-container">$i=1...k-1$</span>, we add a new component for the vectors which is <span class="math-container">$1$</span> for <span class="math-container">$x_i$</span> and <span class="math-container">$x_{i+1}$</span>, <span class="math-container">$2$</span> for <span class="math-container">$y_i$</span> and <span class="math-container">$0$</span> for the others.</p>
<p>For example, By taking the 3-regular hypergraph <span class="math-container">$\{1, 2, 3\}, \{1, 2, 4\}, \{1, 2, 5\}, \{4, 5, 6\}, \{3, 5, 6\}, \{3, 4, 6\}$</span>, we get the following matrix:
<span class="math-container">$$\begin{array}{cc} 
&amp;
\begin{array}{l@{{}={}}c} x_1 &amp; x_2 &amp; x_3 &amp; x_4 &amp; x_5 &amp; x_6 &amp; x_7 &amp; y_1 &amp; y_2 &amp; y_3 &amp; y_4 &amp; y_5 &amp; y_6\\
\end{array}
\\
&amp;
\left[
\begin{array}{ccccccc|cccccc}
1 &amp; 1 &amp; 1 &amp; 0 &amp; 0 &amp; 0 &amp; 1 &amp; 0 &amp; 0 &amp; 0 &amp; 0 &amp; 0 &amp; 0\\
1 &amp; 1 &amp; 1 &amp; 0 &amp; 0 &amp; 0 &amp; 1 &amp; 0 &amp; 0 &amp; 0 &amp; 0 &amp; 0 &amp; 0\\
1 &amp; 0 &amp; 0 &amp; 0 &amp; 1 &amp; 1 &amp; 1 &amp; 0 &amp; 0 &amp; 0 &amp; 0 &amp; 0 &amp; 0\\
0 &amp; 1 &amp; 0 &amp; 1 &amp; 0 &amp; 1 &amp; 1 &amp; 0 &amp; 0 &amp; 0 &amp; 0 &amp; 0 &amp; 0\\
0 &amp; 0 &amp; 1 &amp; 1 &amp; 1 &amp; 0 &amp; 1 &amp; 0 &amp; 0 &amp; 0 &amp; 0 &amp; 0 &amp; 0\\
0 &amp; 0 &amp; 0 &amp; 1 &amp; 1 &amp; 1 &amp; 1 &amp; 0 &amp; 0 &amp; 0 &amp; 0 &amp; 0 &amp; 0\\
\hline
1 &amp; 1 &amp; 0 &amp; 0 &amp; 0 &amp; 0 &amp; 0 &amp; 2 &amp; 0 &amp; 0 &amp; 0 &amp; 0 &amp; 0\\
0 &amp; 1 &amp; 1 &amp; 0 &amp; 0 &amp; 0 &amp; 0 &amp; 0 &amp; 2 &amp; 0 &amp; 0 &amp; 0 &amp; 0\\
0 &amp; 0 &amp; 1 &amp; 1 &amp; 0 &amp; 0 &amp; 0 &amp; 0 &amp; 0 &amp; 2 &amp; 0 &amp; 0 &amp; 0\\
0 &amp; 0 &amp; 0 &amp; 1 &amp; 1 &amp; 0 &amp; 0 &amp; 0 &amp; 0 &amp; 0 &amp; 2 &amp; 0 &amp; 0\\
0 &amp; 0 &amp; 0 &amp; 0 &amp; 1 &amp; 1 &amp; 0 &amp; 0 &amp; 0 &amp; 0 &amp; 0 &amp; 2 &amp; 0\\
0 &amp; 0 &amp; 0 &amp; 0 &amp; 0 &amp; 1 &amp; 1 &amp; 0 &amp; 0 &amp; 0 &amp; 0 &amp; 0 &amp; 2\\
\end{array}
\right]
\end{array}$$</span></p>
<p>From two subsets, we easily build a solution by dispatching the partition from <span class="math-container">$x_1, x_2, ..., x_5$</span> in the two subsets.
For all <span class="math-container">$i=1...k-1$</span>, if <span class="math-container">$x_i$</span> is in a different subset than <span class="math-container">$x_{i+1}$</span> then the
If some <span class="math-container">$x_i$</span> is in one of the subsets, then row <span class="math-container">$x_i$</span> imposes that <span class="math-container">$x_i+1$</span> must also be in a subset. If <span class="math-container">$x_i$</span> and <span class="math-container">$x_{i+1}$</span> are in different subsets, the sums in row <span class="math-container">$3q+i$</span> match, otherwise, we add <span class="math-container">$y_i$</span> to the other subset (so for row <span class="math-container">$3q+i$</span>, we get <span class="math-container">$1+1$</span> in a subset and <span class="math-container">$2$</span> in the other).</p>
<p>Now, suppose we have two disjoint non-empty subsets of vectors that sums to the same vector. We cannot have only <span class="math-container">$y_i$</span> in the subsets, so there is at least a <span class="math-container">$x_i$</span> that is chosen. If <span class="math-container">$x_i$</span> is chosen in a subset, row <span class="math-container">$3q+i$</span> ensure that <span class="math-container">$x_{i+1}$</span> too must appear in on the subsets. Step by step, if one <span class="math-container">$x_i$</span> is in some subset, all the <span class="math-container">$x_i$</span> must belong to a subset, hence we will get a partition of the <span class="math-container">$x_i$</span>.</p>

CC BY-SA 4.0
2024-03-16T00:44:23.483Z
You may want to add details for others to understand/verify your construction.
Chandra Chekuri
CC BY-SA 4.0
2024-03-16T00:11:30.227Z
2024-03-16T12:54:31.100Z
2024-03-16T12:54:31.100Z
caduk
<p><strong>EDIT:</strong> I did not answer the original question about EQUAL SUBSET SUM but instead described a reduction for the PARTITION version. I am leaving it here since the OP found this answer useful. It may be possible to tweak the reduction to show a direct reduction for EQUAL SUBSET SUM.</p>
<p>There seems to be an easy reduction for X3C (Exact-3-Cover) with the additional condition that each element belongs to exactly 3 sets. Equivalently this is a 3DM instance in which the degree of each vertex is exactly 3. Let <span class="math-container">$n$</span> be number of vertices and <span class="math-container">$m = 3n$</span> be number of hyperedges. For each hyperedge <span class="math-container">$e_i$</span> create a <span class="math-container">$n$</span>-dimensional vector with 1 in dimension <span class="math-container">$j$</span> if <span class="math-container">$v_j \in e_i$</span> and 0 otherwise. Create an additional all 1s vector. Total sum of all vectors is the all 4s vector because degree of each vertex is exactly 3. Only way to get the desired partition of vectors is for the vector sum in each part to be the all 2s vector. This is possible only if the set of vectors that are in the part with the all 1s vector correspond to a perfect matching.</p>

CC BY-SA 4.0
2024-03-15T23:32:21.147Z
Thanks, this is for PARTITION right, not EQUAL SUBSET SUM? Still, this interests me to have an easy reduction to PARTITION, with binary values which I did not have (I had either negative values or a bound linear on the number of vectors).
caduk
CC BY-SA 4.0
2024-03-15T20:36:08.867Z
2024-03-16T00:34:11.913Z
2024-03-16T00:34:11.913Z
Chandra Chekuri
<p>I want to show that the multi-dimensional Equal-Subset-Sum is NP-complete in the strong sense:
Given a set of <span class="math-container">$d$</span>-dimensional vectors of non-negative integers, does there exist two distinct nonempty subsets of vectors that sum up to the same vector?</p>
<p>I know from [1] that it is weakly NP-complete when <span class="math-container">$d=1$</span>, but I don't find any references for the strong hardness in the multi-dimensional case when the dimension is part of the input.</p>
<p>The standard path to show that Equal-Subset-Sum is NP-complete is:
<span class="math-container">$\text{ SUBSET SUM } \leq_p \text{ PARTITION } \leq_p \text{ EVEN ODD PARTITION } \leq_p \text{ EQUAL SUBSET SUM }$</span></p>
<p>By mimicking the reductions in a multidimensional way, I can get the result I want, but that seems a long stretch for a result that seems &quot;obvious&quot; at first sight (when knowing that Equal-Subset-Sum is weakly NP-complete)</p>
<p>Are there some shortcuts to get this result?</p>
<p>Some ideas:</p>
<ul>
<li>Can we reduce the scalar version to the multidimensional version by writing the values in some well-chosen basis, with some kind of transformation that avoids carrying in the sum?</li>
<li>Is there some reference directly to one of the problems in the reduction chain?</li>
<li>Can we directly find a completely new reduction to the EQUAL SUBSET SUM?</li>
</ul>
<p>[1] : <em>Woeginger, Gerhard J.; Yu, Zhongliang</em>, <a href="https://doi.org/10.1016/0020-0190(92)90226-L" rel="nofollow noreferrer"><strong>On the equal-subset-sum problem</strong></a>, Inf. Process. Lett. 42, No. 6, 299-302 (1992). <a href="https://zbmath.org/?q=an:0772.68059" rel="nofollow noreferrer">ZBL0772.68059</a>.</p>

CC BY-SA 4.0
2024-03-15T17:17:55.293Z
Have you checked out other proofs of strong NP-hardness?  I think many give reductions from 3D-matching.  The proof that PARTITION-PRODUCT is strongly NP-hard is interesting.   3-PARTITION may also be useful.
Neal Young
CC BY-SA 4.0
2024-03-15T17:55:18.257Z
@NealYoung It is pretty easy from X3C to have the multidimensional case for SUBSET SUM, but I struggle for PARTITION. I just found a reference that shows that finding a $\{-1, 0, 1\}$ eigenvector for $\lambda=1$ is $NP$-complete, and the reduction suggest that it is true even if the matrix is $\{-1, 0, 1\}$, which is basically what I want, except I don't want negative value, but I think that I can reduce from this or adapt the proof.
caduk
<np-hardness><reductions><partition-problem><subset-sum>
strong NP-completeness of multi-dimensional Equal-Subset-Sum
caduk
# strong NP-completeness of multi-dimensional Equal-Subset-Sum

(Asked by: username_0 on 2024-03-15)

I want to show that the multi-dimensional Equal-Subset-Sum is NP-complete in the strong sense:
Given a set of $d$-dimensional vectors of non-negative integers, does there exist two distinct nonempty subsets of vectors that sum up to the same vector?

I know from [1] that it is weakly NP-complete when $d=1$, but I don't find any references for the strong hardness in the multi-dimensional case when the dimension is part of the input.

The standard path to show that Equal-Subset-Sum is NP-complete is:
$\text{ SUBSET SUM } \leq\_p \text{ PARTITION } \leq\_p \text{ EVEN ODD PARTITION } \leq\_p \text{ EQUAL SUBSET SUM }$

By mimicking the reductions in a multidimensional way, I can get the result I want, but that seems a long stretch for a result that seems "obvious" at first sight (when knowing that Equal-Subset-Sum is weakly NP-complete)

Are there some shortcuts to get this result?

Some ideas:

* Can we reduce the scalar version to the multidimensional version by writing the values in some well-chosen basis, with some kind of transformation that avoids carrying in the sum?
* Is there some reference directly to one of the problems in the reduction chain?
* Can we directly find a completely new reduction to the EQUAL SUBSET SUM?

[1] : *Woeginger, Gerhard J.; Yu, Zhongliang*, [**On the equal-subset-sum problem**](https://doi.org/10.1016/0020-0190(92)90226-L), Inf. Process. Lett. 42, No. 6, 299-302 (1992). [ZBL0772.68059](https://zbmath.org/?q=an:0772.68059).

**Tags:** np-hardness, reductions, partition-problem, subset-sum
> **Comments:**
> **username_1**: Have you checked out other proofs of strong NP-hardness?  I think many give reductions from 3D-matching.  The proof that PARTITION-PRODUCT is strongly NP-hard is interesting.   3-PARTITION may also be useful.  
> **username_0**: @NealYoung It is pretty easy from X3C to have the multidimensional case for SUBSET SUM, but I struggle for PARTITION. I just found a reference that shows that finding a $\{-1, 0, 1\}$ eigenvector for $\lambda=1$ is $NP$-complete, and the reduction suggest that it is true even if the matrix is $\{-1, 0, 1\}$, which is basically what I want, except I don't want negative value, but I think that I can reduce from this or adapt the proof.  

---

## 2 answers

### Answer by username_0 on 2024-03-16. Score: 0 | Accepted answer

I think I got a reduction by combining the reduction from @Chandra and idea from other reductions to avoid passing by ODD EVEN PARTITION.

As in Chandra's reduction, we reduce from restricted X3C and build the same vectors $x\_1, ..., x\_k$ of size $3q$. We add $k-1$ new vectors $y\_1, ..., y\_{k-1}$ of zeros. For all $i=1...k-1$, we add a new component for the vectors which is $1$ for $x\_i$ and $x\_{i+1}$, $2$ for $y\_i$ and $0$ for the others.

For example, By taking the 3-regular hypergraph $\{1, 2, 3\}, \{1, 2, 4\}, \{1, 2, 5\}, \{4, 5, 6\}, \{3, 5, 6\}, \{3, 4, 6\}$, we get the following matrix:
$$\begin{array}{cc}
&
\begin{array}{l@{{}={}}c} x\_1 & x\_2 & x\_3 & x\_4 & x\_5 & x\_6 & x\_7 & y\_1 & y\_2 & y\_3 & y\_4 & y\_5 & y\_6\\
\end{array}
\\
&
\left[
\begin{array}{ccccccc|cccccc}
1 & 1 & 1 & 0 & 0 & 0 & 1 & 0 & 0 & 0 & 0 & 0 & 0\\
1 & 1 & 1 & 0 & 0 & 0 & 1 & 0 & 0 & 0 & 0 & 0 & 0\\
1 & 0 & 0 & 0 & 1 & 1 & 1 & 0 & 0 & 0 & 0 & 0 & 0\\
0 & 1 & 0 & 1 & 0 & 1 & 1 & 0 & 0 & 0 & 0 & 0 & 0\\
0 & 0 & 1 & 1 & 1 & 0 & 1 & 0 & 0 & 0 & 0 & 0 & 0\\
0 & 0 & 0 & 1 & 1 & 1 & 1 & 0 & 0 & 0 & 0 & 0 & 0\\
\hline
1 & 1 & 0 & 0 & 0 & 0 & 0 & 2 & 0 & 0 & 0 & 0 & 0\\
0 & 1 & 1 & 0 & 0 & 0 & 0 & 0 & 2 & 0 & 0 & 0 & 0\\
0 & 0 & 1 & 1 & 0 & 0 & 0 & 0 & 0 & 2 & 0 & 0 & 0\\
0 & 0 & 0 & 1 & 1 & 0 & 0 & 0 & 0 & 0 & 2 & 0 & 0\\
0 & 0 & 0 & 0 & 1 & 1 & 0 & 0 & 0 & 0 & 0 & 2 & 0\\
0 & 0 & 0 & 0 & 0 & 1 & 1 & 0 & 0 & 0 & 0 & 0 & 2\\
\end{array}
\right]
\end{array}$$

From two subsets, we easily build a solution by dispatching the partition from $x\_1, x\_2, ..., x\_5$ in the two subsets.
For all $i=1...k-1$, if $x\_i$ is in a different subset than $x\_{i+1}$ then the
If some $x\_i$ is in one of the subsets, then row $x\_i$ imposes that $x\_i+1$ must also be in a subset. If $x\_i$ and $x\_{i+1}$ are in different subsets, the sums in row $3q+i$ match, otherwise, we add $y\_i$ to the other subset (so for row $3q+i$, we get $1+1$ in a subset and $2$ in the other).

Now, suppose we have two disjoint non-empty subsets of vectors that sums to the same vector. We cannot have only $y\_i$ in the subsets, so there is at least a $x\_i$ that is chosen. If $x\_i$ is chosen in a subset, row $3q+i$ ensure that $x\_{i+1}$ too must appear in on the subsets. Step by step, if one $x\_i$ is in some subset, all the $x\_i$ must belong to a subset, hence we will get a partition of the $x\_i$.

> **Comments:**
> **username_2**: You may want to add details for others to understand/verify your construction.  

---

### Answer by username_2 on 2024-03-15. Score: 1

**EDIT:** I did not answer the original question about EQUAL SUBSET SUM but instead described a reduction for the PARTITION version. I am leaving it here since the OP found this answer useful. It may be possible to tweak the reduction to show a direct reduction for EQUAL SUBSET SUM.

There seems to be an easy reduction for X3C (Exact-3-Cover) with the additional condition that each element belongs to exactly 3 sets. Equivalently this is a 3DM instance in which the degree of each vertex is exactly 3. Let $n$ be number of vertices and $m = 3n$ be number of hyperedges. For each hyperedge $e\_i$ create a $n$-dimensional vector with 1 in dimension $j$ if $v\_j \in e\_i$ and 0 otherwise. Create an additional all 1s vector. Total sum of all vectors is the all 4s vector because degree of each vertex is exactly 3. Only way to get the desired partition of vectors is for the vector sum in each part to be the all 2s vector. This is possible only if the set of vectors that are in the part with the all 1s vector correspond to a perfect matching.

> **Comments:**
> **username_0**: Thanks, this is for PARTITION right, not EQUAL SUBSET SUM? Still, this interests me to have an easy reduction to PARTITION, with binary values which I did not have (I had either negative values or a bound linear on the number of vectors).  

---

