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

  • 1
    $\begingroup$ @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. $\endgroup$ Feb 7 at 8:03
  • 1
    $\begingroup$ @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. $\endgroup$ Feb 7 at 12:07
  • 2
    $\begingroup$ @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). $\endgroup$
    – Wei Zhan
    Feb 7 at 13:40
  • 3
    $\begingroup$ @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. $\endgroup$
    – domotorp
    Feb 7 at 13:41
  • 1
    $\begingroup$ 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? $\endgroup$ Feb 7 at 14:56

1 Answer 1


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 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 or in these lecture notes)---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).

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.

  • $\begingroup$ 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). $\endgroup$
    – a3nm
    Feb 12 at 9:50

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

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