<p>This problem is NP hard.  Essentially we can reduce from Partition, though there are some issues that mean we can't reduce from Partition directly.  Instead, we reduce from a Partition-like problem; this problem can in turn be shown to be NP-complete by a (very slight) variant of the standard Partition NP hardness proof.</p>
<p>In particular, the sum of all elements in the array must be <span class="math-container">$m \sum_{s\in S} s$</span>.  This means that in a solution each column must sum to exactly <span class="math-container">$\frac{m}{n}\sum_{s\in S} s$</span>.  So, if we set <span class="math-container">$m = n/2$</span> then each column must sum to <span class="math-container">$\frac{1}{2}\sum_{s\in S} s$</span>.  That leads us to an idea that doesn't quite work. What we'd like to do is start with an even-sized Partition instance <span class="math-container">$S$</span>, set <span class="math-container">$m = n/2$</span>, and claim that a solution array exists if and only if there is a solution to Partition.  Unfortunately, there are problems.  First, the solution must have exactly <span class="math-container">$n/2$</span> elements (this is <a href="https://en.wikipedia.org/wiki/Partition_problem#Variants_and_generalizations" rel="noreferrer">already known</a> to still be NP hard).  Second, a column of the matrix might use elements of <span class="math-container">$S$</span> multiple times.</p>
<p>Basically, the rest of this post shows that these differences don't make a difference: we define a variant of Partition capturing the above restrictions, and then show that the classic Partition NP-hardness proof almost immediately applies to this variant as well.</p>
<p><strong>Partition variant definition:</strong>  Let's define a problem called RestrictedPartition, which is a promise version of Partition with some extra restrictions.  In RestrictedPartition we are given a set <span class="math-container">$S$</span> of positive integers, with the promise that <span class="math-container">$|S|$</span> is even and there is no multiset <span class="math-container">$M$</span>, such that <span class="math-container">$M$</span> is not a set, consisting of <span class="math-container">$n/2$</span> elements of <span class="math-container">$S$</span> such that <span class="math-container">$\sum_{m\in M} = \frac{1}{2}\sum_{s\in S} s$</span>.  (In particular, <span class="math-container">$S$</span> must satisfy that if there is a set of <span class="math-container">$n$</span> nonnegative integers <span class="math-container">$c_1\ldots c_n$</span> such that <span class="math-container">$\sum_{i=1}^n c_i s_i = \frac{1}{2}\sum_{s\in S} s$</span>, then every <span class="math-container">$c_i$</span> must be <span class="math-container">$1$</span> or <span class="math-container">$0$</span>.)  Under this restriction, RestrictedPartition asks to determine if there is a subset <span class="math-container">$S'\subset S$</span> with <span class="math-container">$|S'| = n/2$</span> such that <span class="math-container">$\sum_{s'\in S'} s' = \frac{1}{2} \sum_{s\in S} s$</span>.</p>
<p><strong>Problem is NP hard reducing from RestrictedPartition</strong>  If <span class="math-container">$S$</span> is an instance of RestrictedPartition, the reduction is to create an instance of this problem with the same <span class="math-container">$S$</span> and with <span class="math-container">$m = n/2$</span>.</p>
<p>If ResitrictedPartition has a solution <span class="math-container">$S'$</span> (of size <span class="math-container">$n/2$</span>), we want too show that there is a solution to this problem.  We can set the first column of the final matrix to be <span class="math-container">$S'$</span> in sorted order; the next <span class="math-container">$n/2-1$</span> columns are each constructed by rotating the previous column down one element.  The final <span class="math-container">$n/2$</span> columns can be made the same way with <span class="math-container">$S\setminus S'$</span>.  All columns have the same sum, and all rows must have both all elements of <span class="math-container">$S'$</span> and all elements of <span class="math-container">$S\setminus S'$</span>.</p>
<p>For the other direction, we want to show that if this problem has a solution matrix <span class="math-container">$M$</span>, RestrictedPartition has a solution <span class="math-container">$S'$</span>.  Set <span class="math-container">$S'$</span> to be the first column of <span class="math-container">$M$</span>.  We must have <span class="math-container">$\sum_{s'\in S'} s' = \frac{1}{2}\sum_{s\in S} s$</span> (shown above) and <span class="math-container">$|S'| = n/2$</span>.  By the assumption on <span class="math-container">$S$</span> in RestrictedPartition, all entries in the first column of <span class="math-container">$M$</span> must be unique, so <span class="math-container">$S'$</span> is a set and we are done.</p>
<p><strong>RestrictedPartition is NP hard reducing from 3 dimensional matching</strong> This is basically the classic NP hardness proof for Subset Sum (specifically, the <a href="https://en.wikipedia.org/wiki/Subset_sum_problem#Computational_hardness" rel="noreferrer">one on wikipedia</a> or in <a href="http://www.cs.toronto.edu/%7Elalla/373s16/notes/SS.pdf" rel="noreferrer">these lecture notes</a>)---basically, we can just observe that the classic reduction already satisfies the multiset promise.  Then, we can make a classic change to convert into a Partition instance from a Subset Sum instance, and finally add extra elements to guarantee that there exists a solution with <span class="math-container">$|S'| = n/2$</span>.</p>
<p>We'll begin by creating a set <span class="math-container">$S_1$</span> and a target <span class="math-container">$T$</span> that is essentially an instance of subset sum with the additional promise that no multiset is a solution.  Then, we'll use <span class="math-container">$S_1$</span> and <span class="math-container">$T$</span> to create an instance <span class="math-container">$S$</span> of RestrictedPartition.</p>
<p>(The next three paragraphs are just the classic subset sum hardness proof)  3DM consists of a set of <span class="math-container">$m$</span> edges <span class="math-container">$E$</span>; each edge is a triple <span class="math-container">$(x,y,z)$</span> with <span class="math-container">$x,y,z\in \{1,\ldots, n\}$</span>.  3DM asks if there is a subset <span class="math-container">$E'\subseteq E$</span> such that for any <span class="math-container">$i\in \{1,\ldots, n\}$</span>, there is exactly one <span class="math-container">$e'\in E$</span> such that <span class="math-container">$i$</span> is in the first position in <span class="math-container">$e'$</span>, one <span class="math-container">$e''\in E$</span> such that <span class="math-container">$i$</span> is in the second position in <span class="math-container">$e''$</span>, and one <span class="math-container">$e'''\in E$</span> such that <span class="math-container">$i$</span> is in the third position in <span class="math-container">$e'''$</span>.  (<span class="math-container">$e'$</span>, <span class="math-container">$e''$</span>, and <span class="math-container">$e'''$</span> need not be distinct.)</p>
<p>For each <span class="math-container">$e_i\in E$</span> we create a binary integer <span class="math-container">$n_i$</span>.  We use three helper functions, each of which gives a binary number: <span class="math-container">$x(i) = 10^{n*i + 4n^2}$</span>; <span class="math-container">$y(i) = 10^{n*i + 2n^2}$</span>; <span class="math-container">$z(i) = 10^{n*i}$</span>.
If <span class="math-container">$e_i = (x_i, y_i, z_i)$</span>, then <span class="math-container">$n_i = x(x_i) + y(y_i) + z(z_i)$</span>.  We set <span class="math-container">$S_1 = \bigcup n_i$</span>.  Finally, the target integer <span class="math-container">$T = \sum_{i = 1}^n x(i) + y(i) + z(i)$</span>.</p>
<p>We're immediately done.  If there is a <span class="math-container">$E'\subseteq E$</span> that is a solution to the 3DM instance, there is a subset of <span class="math-container">$S_1$</span> that sums to <span class="math-container">$T$</span> (each entry contributes exactly 3 of the set bits of <span class="math-container">$T$</span>).  Furthermore, no <em>multiset</em> of at most <span class="math-container">$n$</span> elements from <span class="math-container">$S_1$</span> can sum to <span class="math-container">$T$</span> unless that subset corresponds to such an <span class="math-container">$E'$</span> because each set bit is <span class="math-container">$n$</span> away from any other set bit in all numbers in <span class="math-container">$S_1$</span>.  This is because carries don't matter: <span class="math-container">$T$</span> has (for example) a set bit in position <span class="math-container">$p = n\cdot x_i + 4n^2$</span> due to <span class="math-container">$x_i$</span>, and no other set bits in positions <span class="math-container">${p - n/2\ldots, p + n/2}$</span>.  Every element in <span class="math-container">$S_1$</span> also has no set bits in positions <span class="math-container">${p - n/2\ldots p-1}\cup {p_1,\ldots p+n/2}$</span>, so if a (multi)subset of <span class="math-container">$S_1$</span> of cardinality at most <span class="math-container">$n/2$</span> sums to <span class="math-container">$T$</span>, it must have exactly one entry with <span class="math-container">$x_i$</span> set.  Applying the same argument to each <span class="math-container">$y_i$</span> and <span class="math-container">$z_i$</span>, we are done.</p>
<p>(Now we reduce from Subset Sum to RestrictedPartition.)
We then add to <span class="math-container">$S_1$</span> two elements <span class="math-container">$z_1 = \sum_{s_1\in S_1} s_1$</span> and <span class="math-container">$z_2 = T$</span> to obtain <span class="math-container">$S_2 = S_1\cup \{z_1\} \cup \{z_2\}$</span>.  <span class="math-container">$S_2$</span> has a Partition solution if and only if a subset of <span class="math-container">$S_1$</span> sums to <span class="math-container">$T$</span> (this is the classic Partition proof; again see <a href="https://en.wikipedia.org/wiki/Partition_problem#Computational_hardness" rel="noreferrer">wikipedia</a>).</p>
<p>Finally, we need to guarantee that a solution has size exactly <span class="math-container">$|S|/2$</span>---note that the standard technique of adding <span class="math-container">$0$</span>s to <span class="math-container">$S_2$</span> doesn't work since we need all numbers to be positive.  Instead we create <span class="math-container">$|S_2|$</span> sets of three binary numbers: <span class="math-container">$M_i = \{m^1_i, m^2_i, m^3_i\}$</span> for <span class="math-container">$i = 1, \ldots, |S_2|$</span>, where <span class="math-container">$m^1_i = 10^{i*n^2 + n^5}$</span>, <span class="math-container">$m^2_i = 100^{i*n^2 + n^5}$</span>, <span class="math-container">$m^3_i = 110^{i*n^2 + n^5}$</span>.  In particular, for all <span class="math-container">$i$</span>, <span class="math-container">$m^1_i + m^2_i = m_3^i$</span>. We define <span class="math-container">$M = \bigcup M_i$</span> and <span class="math-container">$S = S_2 \cup M$</span>.   Since all numbers in <span class="math-container">$M$</span> are much bigger than any number in <span class="math-container">$S_2$</span>, any partition <span class="math-container">$S'$</span> of <span class="math-container">$S$</span> must have, for all <span class="math-container">$i$</span>, either:  (1) both <span class="math-container">$m^1_i$</span> and <span class="math-container">$m^2_i$</span>, but not <span class="math-container">$m^3_i$</span>, or (2) only <span class="math-container">$m^3_i$</span>, but not <span class="math-container">$m^2_i$</span> or <span class="math-container">$m^1_i$</span> (this is essentially the same argument we used in the 3DM reduction: the bits are so spaced apart that the only (multi) subset of <span class="math-container">$S$</span> that can account for the set bits in <span class="math-container">$m^3_i$</span> are from <span class="math-container">$m^2_i$</span> and <span class="math-container">$m^1_i$</span>).  Note that <span class="math-container">$S$</span> has size <span class="math-container">$|S_2| + 3|S_2|$</span> which is even.</p>
<p>So, if <span class="math-container">$S_2$</span> has a partition <span class="math-container">$S''$</span>, then <span class="math-container">$S$</span> has a partition of size <span class="math-container">$|S|/2$</span>:   <span class="math-container">$M' = m^1_1\cup m^2_1 \cup m^1_2 \cup m^2_2 \ldots \cup m^1_{|S_2| - |S''|} \cup m^2_{|S_2| - |S''|}$</span> and <span class="math-container">$M'' = m^3_{|S_2|- |S''| + 1} \cup \ldots \cup m^3_{|S_2|}$</span>; then <span class="math-container">$S''\cup M' \cup M''$</span> is a partition of <span class="math-container">$S$</span> of size <span class="math-container">$|S''| + 2(|S_2| - |S''|) + |S''| = 2|S_2| = |S|/2$</span>.  For the other direction, if <span class="math-container">$S$</span> has a partition <span class="math-container">$S'$</span>, then <span class="math-container">$S' \cap S_2$</span> must be a partition of <span class="math-container">$S_2$</span> (by the above argument that if <span class="math-container">$m^3_i$</span> is in <span class="math-container">$S''$</span> then <span class="math-container">$m^2_i$</span> and <span class="math-container">$m^1_i$</span> are in <span class="math-container">$S_2\setminus S''$</span>, and vice versa).  Then we are done.</p>

CC BY-SA 4.0
2023-02-12T09:50:40.967Z
Interesting, thanks! I'm still wondering though whether the problem with fixed $m$ (e.g., $m=3$) is also NP-hard; and whether strong NP-hardness can hold (i.e., the input numbers are given in unary; which doesn't seem to be the case in your proof).
Antoine Amarilli 'a3nm'
CC BY-SA 4.0
2023-02-09T22:31:07.577Z
2023-02-09T22:31:07.577Z
SamM
<p>Does the following problem have a name? Is it NP-complete?</p>
<p>Given a multiset of <span class="math-container">$n$</span> positive integers, <span class="math-container">$S$</span>, and an positive integer <span class="math-container">$m$</span>, does there exist an <span class="math-container">$m \times n$</span> matrix whose rows are permutations of <span class="math-container">$S$</span> and whose columns all have equal sum?</p>
<p>Example: <span class="math-container">$S = [1,2,2,3]$</span>, <span class="math-container">$m=2$</span>.
Solution:
<span class="math-container">$$
A = 
\begin{pmatrix}
1 &amp; 2 &amp; 2 &amp; 3
\\ 3 &amp; 2 &amp; 2 &amp; 1
\end{pmatrix}.
$$</span></p>

CC BY-SA 4.0
2023-02-07T06:41:08.337Z
Is it trivially in NP? Clearly there is always a solution if you take $m=n!$ (by listing all the permutations), so I assume you mean that we are given a bound $k$ and we ask if we can solve it below $k$. But if $k$ is given in binary, it's not clear that this is solvable in NP (if $k$ is in unary then yes).
Shaull
CC BY-SA 4.0
2023-02-07T08:03:54.963Z
@Shaull You are *given* $m$ as part of the input, so a bound $k$ is redundant. But as you say, it should presumably be given in unary if the problem is to be in NP.
Emil Jeřábek
CC BY-SA 4.0
2023-02-07T11:11:24.040Z
@EmilJeřábek - right, sorry, I meant $m$, not $k$. But the same comment applies. Why do you say it should be given in unary? Is the problem trivially NP-hard if it's in binary?
Shaull
CC BY-SA 4.0
2023-02-07T12:07:00.230Z
@Shaull I was just expressing agreement with what you wrote: that if it is given in binary, the problem doesn’t look like it is in NP in the first place.
Emil Jeřábek
CC BY-SA 4.0
2023-02-07T13:40:52.517Z
@EmilJeřábek It is in NP even with binary $m$. The witness can be each column expressed as a multiset of size $m$ in $[n]$ (indexing the numbers in $S$), which overall takes $O(n^2\log m)$ bits to describe. If each index in $[n]$ appears in total exactly $m$ times, there must be an arrangement such that each row is a permutation (you can fix the first row by Hall's theorem and use induction on the rest).
Wei Zhan
CC BY-SA 4.0
2023-02-07T13:41:35.350Z
@Shaull I don't understand why you wrote $m=n!$, you could also take $m=n$ and the cyclic permutations. But I think that the question is about a fixed exact $m$, and not about an at most $m$ number of rows.
domotorp
CC BY-SA 4.0
2023-02-07T14:47:37.847Z
@WeiZhan Oh I see, thank you.
Emil Jeřábek
CC BY-SA 4.0
2023-02-07T14:56:17.183Z
So the problem is equivalent to: does there exist an $n\times n$  non-negative integer matrix $M$ such that $M(1,\dots,1)^T=(m,\dots,m)^T$ and $SM$ is a constant vector?
Emil Jeřábek
CC BY-SA 4.0
2023-02-07T15:14:14.030Z
Nice question! For the constant value $m=3$, this looks very related to the NP-hard problem https://en.wikipedia.org/wiki/Numerical_3-dimensional_matching. This implies that the problem of the question is hard for $m=3$ if you enforce a restrictions on the permutations used on the three rows. I wasn't able to show NP-hardness of the original formulation, however, but maybe there is a trick I did not see.
Antoine Amarilli 'a3nm'
CC BY-SA 4.0
2023-02-07T18:54:19.190Z
Specifically for $m=3$ the question is in fact equivalent to asking whether the numerical 3-dimensional matching problem is still NP-hard if the three multisets $A$ and $B$ and $C$ are identical. This sounds like a very natural question -- unfortunately I wasn't able to find papers or an argument addressing this.
Antoine Amarilli 'a3nm'
CC BY-SA 4.0
2023-02-07T21:07:04.247Z
@EmilJeřábek, Don't you also need the constraint $(1, \ldots, 1)M = (m, \ldots, m)$?  (Because you need both that each column contains $m$ elements total, and that each element is used $m$ times.)  (And this also ensures that $M$ is the sum of $m$ permutation matrices.)
Neal Young
CC BY-SA 4.0
2023-02-07T21:20:13.250Z
@NealYoung You are right.
Emil Jeřábek
CC BY-SA 4.0
2023-02-08T08:42:14.640Z
@EmilJeřábek The title "is this a known problem" ;)
mathworker21
<np-hardness>
Is this a known problem, and is it NP-complete?
Ben G
# Is this a known problem, and is it NP-complete?

(Asked by: username_0 on 2023-02-06)

Does the following problem have a name? Is it NP-complete?

Given a multiset of $n$ positive integers, $S$, and an positive integer $m$, does there exist an $m \times n$ matrix whose rows are permutations of $S$ and whose columns all have equal sum?

Example: $S = [1,2,2,3]$, $m=2$.
Solution:
$$
A =
\begin{pmatrix}
1 & 2 & 2 & 3
\\ 3 & 2 & 2 & 1
\end{pmatrix}.
$$

**Tags:** np-hardness
> **Comments:**
> **username_1**: Is it trivially in NP? Clearly there is always a solution if you take $m=n!$ (by listing all the permutations), so I assume you mean that we are given a bound $k$ and we ask if we can solve it below $k$. But if $k$ is given in binary, it's not clear that this is solvable in NP (if $k$ is in unary then yes).  
> **username_2**: @Shaull You are *given* $m$ as part of the input, so a bound $k$ is redundant. But as you say, it should presumably be given in unary if the problem is to be in NP.  
> **username_1**: @EmilJeřábek - right, sorry, I meant $m$, not $k$. But the same comment applies. Why do you say it should be given in unary? Is the problem trivially NP-hard if it's in binary?  
> **username_2**: @Shaull I was just expressing agreement with what you wrote: that if it is given in binary, the problem doesn’t look like it is in NP in the first place.  
> **username_3**: @EmilJeřábek It is in NP even with binary $m$. The witness can be each column expressed as a multiset of size $m$ in $[n]$ (indexing the numbers in $S$), which overall takes $O(n^2\log m)$ bits to describe. If each index in $[n]$ appears in total exactly $m$ times, there must be an arrangement such that each row is a permutation (you can fix the first row by Hall's theorem and use induction on the rest).  
> **username_4**: @Shaull I don't understand why you wrote $m=n!$, you could also take $m=n$ and the cyclic permutations. But I think that the question is about a fixed exact $m$, and not about an at most $m$ number of rows.  
> **username_2**: @WeiZhan Oh I see, thank you.  
> **username_2**: So the problem is equivalent to: does there exist an $n\times n$  non-negative integer matrix $M$ such that $M(1,\dots,1)^T=(m,\dots,m)^T$ and $SM$ is a constant vector?  
> **username_5**: Nice question! For the constant value $m=3$, this looks very related to the NP-hard problem https://en.wikipedia.org/wiki/Numerical_3-dimensional_matching. This implies that the problem of the question is hard for $m=3$ if you enforce a restrictions on the permutations used on the three rows. I wasn't able to show NP-hardness of the original formulation, however, but maybe there is a trick I did not see.  
> **username_5**: Specifically for $m=3$ the question is in fact equivalent to asking whether the numerical 3-dimensional matching problem is still NP-hard if the three multisets $A$ and $B$ and $C$ are identical. This sounds like a very natural question -- unfortunately I wasn't able to find papers or an argument addressing this.  
> **username_6**: @EmilJeřábek, Don't you also need the constraint $(1, \ldots, 1)M = (m, \ldots, m)$?  (Because you need both that each column contains $m$ elements total, and that each element is used $m$ times.)  (And this also ensures that $M$ is the sum of $m$ permutation matrices.)  
> **username_2**: @NealYoung You are right.  
> **username_7**: @EmilJeřábek The title "is this a known problem" ;)  

---

## 1 answers

### Answer by username_8 on 2023-02-09. Score: 7 | Accepted answer

This problem is NP hard. Essentially we can reduce from Partition, though there are some issues that mean we can't reduce from Partition directly. Instead, we reduce from a Partition-like problem; this problem can in turn be shown to be NP-complete by a (very slight) variant of the standard Partition NP hardness proof.

In particular, the sum of all elements in the array must be $m \sum\_{s\in S} s$. This means that in a solution each column must sum to exactly $\frac{m}{n}\sum\_{s\in S} s$. So, if we set $m = n/2$ then each column must sum to $\frac{1}{2}\sum\_{s\in S} s$. That leads us to an idea that doesn't quite work. What we'd like to do is start with an even-sized Partition instance $S$, set $m = n/2$, and claim that a solution array exists if and only if there is a solution to Partition. Unfortunately, there are problems. First, the solution must have exactly $n/2$ elements (this is [already known](https://en.wikipedia.org/wiki/Partition_problem#Variants_and_generalizations) to still be NP hard). Second, a column of the matrix might use elements of $S$ multiple times.

Basically, the rest of this post shows that these differences don't make a difference: we define a variant of Partition capturing the above restrictions, and then show that the classic Partition NP-hardness proof almost immediately applies to this variant as well.

**Partition variant definition:** Let's define a problem called RestrictedPartition, which is a promise version of Partition with some extra restrictions. In RestrictedPartition we are given a set $S$ of positive integers, with the promise that $|S|$ is even and there is no multiset $M$, such that $M$ is not a set, consisting of $n/2$ elements of $S$ such that $\sum\_{m\in M} = \frac{1}{2}\sum\_{s\in S} s$. (In particular, $S$ must satisfy that if there is a set of $n$ nonnegative integers $c\_1\ldots c\_n$ such that $\sum\_{i=1}^n c\_i s\_i = \frac{1}{2}\sum\_{s\in S} s$, then every $c\_i$ must be $1$ or $0$.) Under this restriction, RestrictedPartition asks to determine if there is a subset $S'\subset S$ with $|S'| = n/2$ such that $\sum\_{s'\in S'} s' = \frac{1}{2} \sum\_{s\in S} s$.

**Problem is NP hard reducing from RestrictedPartition** If $S$ is an instance of RestrictedPartition, the reduction is to create an instance of this problem with the same $S$ and with $m = n/2$.

If ResitrictedPartition has a solution $S'$ (of size $n/2$), we want too show that there is a solution to this problem. We can set the first column of the final matrix to be $S'$ in sorted order; the next $n/2-1$ columns are each constructed by rotating the previous column down one element. The final $n/2$ columns can be made the same way with $S\setminus S'$. All columns have the same sum, and all rows must have both all elements of $S'$ and all elements of $S\setminus S'$.

For the other direction, we want to show that if this problem has a solution matrix $M$, RestrictedPartition has a solution $S'$. Set $S'$ to be the first column of $M$. We must have $\sum\_{s'\in S'} s' = \frac{1}{2}\sum\_{s\in S} s$ (shown above) and $|S'| = n/2$. By the assumption on $S$ in RestrictedPartition, all entries in the first column of $M$ must be unique, so $S'$ is a set and we are done.

**RestrictedPartition is NP hard reducing from 3 dimensional matching** This is basically the classic NP hardness proof for Subset Sum (specifically, the [one on wikipedia](https://en.wikipedia.org/wiki/Subset_sum_problem#Computational_hardness) or in [these lecture notes](http://www.cs.toronto.edu/%7Elalla/373s16/notes/SS.pdf))---basically, we can just observe that the classic reduction already satisfies the multiset promise. Then, we can make a classic change to convert into a Partition instance from a Subset Sum instance, and finally add extra elements to guarantee that there exists a solution with $|S'| = n/2$.

We'll begin by creating a set $S\_1$ and a target $T$ that is essentially an instance of subset sum with the additional promise that no multiset is a solution. Then, we'll use $S\_1$ and $T$ to create an instance $S$ of RestrictedPartition.

(The next three paragraphs are just the classic subset sum hardness proof) 3DM consists of a set of $m$ edges $E$; each edge is a triple $(x,y,z)$ with $x,y,z\in \{1,\ldots, n\}$. 3DM asks if there is a subset $E'\subseteq E$ such that for any $i\in \{1,\ldots, n\}$, there is exactly one $e'\in E$ such that $i$ is in the first position in $e'$, one $e''\in E$ such that $i$ is in the second position in $e''$, and one $e'''\in E$ such that $i$ is in the third position in $e'''$. ($e'$, $e''$, and $e'''$ need not be distinct.)

For each $e\_i\in E$ we create a binary integer $n\_i$. We use three helper functions, each of which gives a binary number: $x(i) = 10^{n\*i + 4n^2}$; $y(i) = 10^{n\*i + 2n^2}$; $z(i) = 10^{n\*i}$.
If $e\_i = (x\_i, y\_i, z\_i)$, then $n\_i = x(x\_i) + y(y\_i) + z(z\_i)$. We set $S\_1 = \bigcup n\_i$. Finally, the target integer $T = \sum\_{i = 1}^n x(i) + y(i) + z(i)$.

We're immediately done. If there is a $E'\subseteq E$ that is a solution to the 3DM instance, there is a subset of $S\_1$ that sums to $T$ (each entry contributes exactly 3 of the set bits of $T$). Furthermore, no *multiset* of at most $n$ elements from $S\_1$ can sum to $T$ unless that subset corresponds to such an $E'$ because each set bit is $n$ away from any other set bit in all numbers in $S\_1$. This is because carries don't matter: $T$ has (for example) a set bit in position $p = n\cdot x\_i + 4n^2$ due to $x\_i$, and no other set bits in positions ${p - n/2\ldots, p + n/2}$. Every element in $S\_1$ also has no set bits in positions ${p - n/2\ldots p-1}\cup {p\_1,\ldots p+n/2}$, so if a (multi)subset of $S\_1$ of cardinality at most $n/2$ sums to $T$, it must have exactly one entry with $x\_i$ set. Applying the same argument to each $y\_i$ and $z\_i$, we are done.

(Now we reduce from Subset Sum to RestrictedPartition.)
We then add to $S\_1$ two elements $z\_1 = \sum\_{s\_1\in S\_1} s\_1$ and $z\_2 = T$ to obtain $S\_2 = S\_1\cup \{z\_1\} \cup \{z\_2\}$. $S\_2$ has a Partition solution if and only if a subset of $S\_1$ sums to $T$ (this is the classic Partition proof; again see [wikipedia](https://en.wikipedia.org/wiki/Partition_problem#Computational_hardness)).

Finally, we need to guarantee that a solution has size exactly $|S|/2$---note that the standard technique of adding $0$s to $S\_2$ doesn't work since we need all numbers to be positive. Instead we create $|S\_2|$ sets of three binary numbers: $M\_i = \{m^1\_i, m^2\_i, m^3\_i\}$ for $i = 1, \ldots, |S\_2|$, where $m^1\_i = 10^{i\*n^2 + n^5}$, $m^2\_i = 100^{i\*n^2 + n^5}$, $m^3\_i = 110^{i\*n^2 + n^5}$. In particular, for all $i$, $m^1\_i + m^2\_i = m\_3^i$. We define $M = \bigcup M\_i$ and $S = S\_2 \cup M$. Since all numbers in $M$ are much bigger than any number in $S\_2$, any partition $S'$ of $S$ must have, for all $i$, either: (1) both $m^1\_i$ and $m^2\_i$, but not $m^3\_i$, or (2) only $m^3\_i$, but not $m^2\_i$ or $m^1\_i$ (this is essentially the same argument we used in the 3DM reduction: the bits are so spaced apart that the only (multi) subset of $S$ that can account for the set bits in $m^3\_i$ are from $m^2\_i$ and $m^1\_i$). Note that $S$ has size $|S\_2| + 3|S\_2|$ which is even.

So, if $S\_2$ has a partition $S''$, then $S$ has a partition of size $|S|/2$: $M' = m^1\_1\cup m^2\_1 \cup m^1\_2 \cup m^2\_2 \ldots \cup m^1\_{|S\_2| - |S''|} \cup m^2\_{|S\_2| - |S''|}$ and $M'' = m^3\_{|S\_2|- |S''| + 1} \cup \ldots \cup m^3\_{|S\_2|}$; then $S''\cup M' \cup M''$ is a partition of $S$ of size $|S''| + 2(|S\_2| - |S''|) + |S''| = 2|S\_2| = |S|/2$. For the other direction, if $S$ has a partition $S'$, then $S' \cap S\_2$ must be a partition of $S\_2$ (by the above argument that if $m^3\_i$ is in $S''$ then $m^2\_i$ and $m^1\_i$ are in $S\_2\setminus S''$, and vice versa). Then we are done.

> **Comments:**
> **username_5**: Interesting, thanks! I'm still wondering though whether the problem with fixed $m$ (e.g., $m=3$) is also NP-hard; and whether strong NP-hardness can hold (i.e., the input numbers are given in unary; which doesn't seem to be the case in your proof).  

---

