2
$\begingroup$

I want to know whats the complexity of the following variant of the partition problem:

Partition problem:

http://en.wikipedia.org/wiki/Partition_problem

Suppose we have one set formed by integers and we want to partition the set in two subsets of the same size, the same cardinality(the same number of integers in each subset) in such a way that each subset equal a given number called S.

Let's call this problem "2-partition" like the 3 partition problem

What's the complexity of the problem is easier,is in P?

Is still in NP?

I tried looking on google but i didn`t found anything, i dont even know if the problem is mentioned in some book or publication

Thanks

|cite|improve this question
$\endgroup$
  • $\begingroup$ So basically what you're asking for is the "normal" partition problem with the addition that the number of elements from each set is equal, correct? $\endgroup$ – john_leo Nov 9 '14 at 18:00
  • $\begingroup$ Yes, that's exactly what i'm asking $\endgroup$ – rotia Nov 9 '14 at 19:02
3
$\begingroup$

Is it in NP? Yes - any restricted version of an NP problem is also in NP.

Is it still NP-hard? Yes. 2-partition (without the constraint that both subsets should be equal cardinality) is NP-hard. Let's call your form of the problem "equal cardinalty 2-partition". To reduce from regular 2-partition to equal cardinalty 2-partition, we can pad the 2-partition problem by adding lots of extra 0's to the set, so that the 0's can be used to balance out any valid 2-partition solution to a solution that is an equal cardinality 2-partition.

You might object to the use of 0's in the input, and define "positive balanced cardinality 2-partition" where the input must be positive (so 0's are not allowed). But I can reduce any balanced cardinalty 2-partition problem to positive balanced cardinalty 2-partition by incrementing all numbers in the input by 1. This does not change the solution because of the equal cardinality constraint (each part of the partition gets increased by equally much).

Now you might still object that this reduction requires that you allow duplicate numbers in the input set. Even if you disallow duplicates in the input it remains NP-hard, and you can show so by a reduction from Positive 1-IN-3 SAT.

Is it in P? Answering this question would settle the P vs. NP problem so you're not very likely to get an answer any time soon.

|cite|improve this answer
$\endgroup$

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.