0
$\begingroup$

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?

|cite|improve this question
$\endgroup$
2
$\begingroup$

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.

|cite|improve this answer
$\endgroup$
  • $\begingroup$ If $G=\{1,2\}$ and $k=2$, there is no solution to this question but there is a subset $\{2\}$ whose sum is 2. $\endgroup$ – Apass.Jack Dec 12 '18 at 6:42
  • $\begingroup$ @Apass.Jack: That's true; I should have mentioned the transformation from subset sum problem to multiset partition problem, and now I have. $\endgroup$ – rici Dec 12 '18 at 22:48
  • $\begingroup$ Nice explanation. $\endgroup$ – Apass.Jack Dec 13 '18 at 0:01
  • $\begingroup$ 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)}$. $\endgroup$ – Apass.Jack Dec 13 '18 at 0:02
  • $\begingroup$ @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. $\endgroup$ – rici Dec 13 '18 at 0:06

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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