1
$\begingroup$

I want to partition a set of numbers in two sets such that their sum is equal. Here in the original master set we can have positive as well as negative numbers. Can anyone tell me about the complexity of this problem. Partition with only positive numbers is NP hard.

$\endgroup$
2
  • $\begingroup$ Well, if Partition with positive numbers is NP-hard, Partition with positive and negative numbers is as well since it includes Partition with positive numbers $\endgroup$
    – fontanf
    Jul 5, 2022 at 8:25
  • $\begingroup$ agreed. But what about the subclass of problems where atleast one number is negative? The same argument would not work. $\endgroup$ Jul 5, 2022 at 17:52

1 Answer 1

2
$\begingroup$

Let $I = \{a_i, i = 1, \dots, n \}$ be an instance of "Partition with only positive numbers" that we want to solve.

Let $I' = \{4 a_i, i = 1, \dots, n \} \cup \{ -1, -1 \}$ be an instance of "Partition with at least one negative number".

  • If $I'$ is "yes", then the two -1 cannot belong to the same partition. Otherwise, one would be a multiple of 4 and the other wouldn't. Therefore, $I$ is "yes" too.
  • If $I$ is "yes", then $I'$ is "yes" too since we can use the same partitions and put a -1 in each partition. Therefore, if $I'$ is "no", then $I$ is "no" too (converse proposition).

So if we were able to solve "Partition with at least one negative number" in polynomial time, we could solve "Partition with only positive number" in polynomial time as well.

$\endgroup$
2
  • $\begingroup$ This seems nice. I guess even subset-sum is hard as well by the same argument? $\endgroup$ Jul 6, 2022 at 14:56
  • $\begingroup$ Subset sum is an optimization problem. The decision version where the value to find is fixed includes Partition. $\endgroup$
    – fontanf
    Jul 6, 2022 at 16:07

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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