# Is this a known problem, and is it NP-complete?

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

• @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. Commented Feb 7, 2023 at 8:03
• @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. Commented Feb 7, 2023 at 12:07
• @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). Commented Feb 7, 2023 at 13:40
• @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. Commented Feb 7, 2023 at 13:41
• 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? Commented Feb 7, 2023 at 14:56

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.

• 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).
– a3nm
Commented Feb 12, 2023 at 9:50