Consider the following problem SQUARED-SUM-PARTITION. You are given positive integers $x_1, \dots, x_n$, and numbers $k$ and $B$. You want to know whether it is possible to partition the numbers $\{ x_i \}$ into $k$ sets $S_1, \dots, S_k$ so that the squared sums of the sets add up to at most $B$: $$ \sum_{i=1}^k \left( \sum_{x_j \in S_i} x_j \right)^2 \leq B $$ Show that this problem is NP-complete.

My solution:

We know that the PARTITION problem (Partition a set of numbers into two sets with equal sum) is NP-complete. Let $S = \{ x_1, \dots, x_n \}$ be an instance of PARTITION. Let $T$ be the sum of all elements in $S$. Then we construct instance of SQUARED-SUM-PARTITION by setting $B = (T/2)^2$ and $k=2$ and $S$ remains the same. Then there is a solution for this instance of SQUARED-SUM-PARTITION if and only if there is a solution for PARTITION.

Can I check if this solution is correct? Does anyone have other interesting ways to solve this?

  • $\begingroup$ $(T/2)^2$ is the sum of one of the halves. The value of B should be $T^2 /2$ $\endgroup$ – narek Bojikian Dec 7 '19 at 3:53
  • $\begingroup$ To prove correctness try to prove the implication in both directions, i.e. if the instance of set partitioning is a yes instance then the instance you built is also a yes instance and if the isnatnce you built is a yes instance then so is the given instance of the set partitioning problem. $\endgroup$ – narek Bojikian Dec 7 '19 at 3:55
  • $\begingroup$ We discourage "please check whether my answer is correct" questions, as only "yes/no" answers are possible, which won't help you or future visitors. See here and here. Can you edit your post to ask about a specific conceptual issue you're uncertain about? As a rule of thumb, a good conceptual question should be useful even to someone who isn't looking at the problem you happen to be working on. If you just need someone to check your work, you might seek out a friend, classmate, or teacher. $\endgroup$ – D.W. Dec 7 '19 at 22:16
  • $\begingroup$ @D.W. Thanks for the feedback, I will try to make the conceptual issues more clear. For this particular question, my main reason was that I wanted to see if there are any other interesting ways to solve this question, because I want to see more kinds of reductions / creative ways to reduce problems to one another. To do this, I had to include my own solution (so that I can avoid comments such as "this is a homework question" or "please at least attempt the question yourself"), and if my solution is correct, other people attempting this question can also view it. $\endgroup$ – eatfood Dec 8 '19 at 11:36
  • $\begingroup$ Please do let me know if there are better ways to achieve the purposes above; I don't want to be breaking the rules / guidelines of this site! $\endgroup$ – eatfood Dec 8 '19 at 11:38

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.