0
$\begingroup$

I hope someone can take some time to consider the following problem and welcome to discuss together.

Number partition problem is one of well-known NP-hard problems.

Now I am considering the hardness of constrained partition problem. In particular, the cardinality of multiset $S$ is n, denoted by $|S|=n$. Now is it NP-completeness to determine whether a given multiset $S$ of positive integers can be partitioned into two subsets $S_1$ and $S_2$ such that the sum of the numbers in $S_1$ equals the sum of the numbers in S2, and subjected to the cardinality of sub multiset $S_1$ is equals $k$, that is $|S_1|=k$ where $k <= n$

$\endgroup$
3
  • $\begingroup$ Did you try the reduction from Number partition problem? $\endgroup$ Aug 29 '21 at 4:25
  • $\begingroup$ Intuitively, i think the constrained number partition is harder than that original one $\endgroup$
    – Jack Zhou
    Aug 29 '21 at 7:27
  • $\begingroup$ You are right! For a formal proof, try to show a polynomial-time reduction from the Number partition problem to the constrained number partition problem. It is not that difficult. $\endgroup$ Aug 29 '21 at 7:46

Your Answer

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

Browse other questions tagged or ask your own question.