Computer Science Stack Exchange is a question and answer site for students, researchers and practitioners of computer science. It only takes a minute to sign up.
Sign up to join this community
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.
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.
