# Complexity of a set partition derived problem

I am stuck at the complexity of the following problem: Given a multiset $$S = \{x_1,..., x_n\}$$ of $$n$$ integers and a natural number $$k$$. Can $$S$$ be partitioned into multisets $$S_1,... S_j$$ such that for all $$S_i \subseteq S$$ there is $$\sum_{ s \in S_i} s = k?$$

I have found out that this may be somehow related to the EqualSubetSum Problem or the partition problem. But is this problem really $$NP$$-complete or exists a polynomial algorithm depending on $$k$$ and $$n$$ to decide this problem?

A set is a multiset (in which every element occurs once) and your partition problem can be used to find a subset of $$S$$ whose sum is $$k$$. [Note 1] So if there were a polynomial-time solution to your partition problem, it could easily be used to solve the subset sum problem in the same amount of time.

So the problem is NP-complete, but that doesn't stop it from having a pseudo-polynomial time solution. There are well-known DP algorithms to solve the subset sum problem which are polynomial in the magnitude of the inputs. Time complexity is always expressed as a function of the size of the inputs, as measured (for example) by the number of bits it takes to represent the input. The magnitude of a number is exponential in the size of the number (eg, a number represented in 100 bits could be as large as $$2^{100}$$). So time complexity polynomial in magnitude is still exponential in problem size.

In your problem, $$n$$ is a measure of problem size, whereas $$k$$ only measures numeric magnitude. So they are very different kinds of parameter.

Here's another longer explanation of pseudo-polynomial time in a StackOverflow answer.

### Notes

1. Let $$S$$ be a set for which we seek a subset whose sum is $$k$$. Without loss of generality, we can assume that $$\Sigma S \le 2k$$ (because a solution for $$k' = \Sigma S - k$$ leads directly to a solution for $$k$$ using the set difference from $$S$$.) If $$\Sigma S = 2k$$ then a solution to the multiset partition problem yields two solutions to the subset sum problem. Otherwise, we form the multiset $$S' = S \cup \{2k - \Sigma S\}$$. Obviously, $$\Sigma S' = 2k$$ and the element we added has a value less than $$k$$. We then compute the multiset partition of $$\langle S', k\rangle$$, which must be a partition into two pieces, at most one of which is a multiset (because there is at most one repeated element in $$S'$$, the one we added). If the first subset in the partition does not include the element we added, it is a solution to the original problem; otherwise, the second subset is.

Computing $$\Sigma S$$ and examining the result of the multiset partition solution are both linear time. So if the multiset partition algorithm were polynomial time, so would be the derived subset sum algorithm.

• If $G=\{1,2\}$ and $k=2$, there is no solution to this question but there is a subset $\{2\}$ whose sum is 2. – John L. Dec 12 '18 at 6:42
• @Apass.Jack: That's true; I should have mentioned the transformation from subset sum problem to multiset partition problem, and now I have. – rici Dec 12 '18 at 22:48
• Nice explanation. – John L. Dec 13 '18 at 0:01
• Have you answered the question, "a polynomial algorithm depending on k and n"? That means, I assume, time-complexity of $k^{O(1)}n^{O(1)}$. – John L. Dec 13 '18 at 0:02
• @Apass.Jack: yes, that is what the expression means, I guess, and I think I did answer it: yes, there (probably) is a dynamic programming algorithm which is polynomial in $k$ but that's really pseudo-polynomial time because it is based on the magnitude of the input, not the size. In other words, the existence of a pseudo-polynomial time algorithm doesn't disprove the NP-completeness of the problem. I put the Wikipedia link in because it seems to be a complicated distinction to make and it didn't seem useful to dump it all into this answer. – rici Dec 13 '18 at 0:06