Related questions:
Let's assume I have a list, which contains exactly 2k
elements. Now, I'm willing to split it into two parts, where each part has a length of k
while trying to make the sum of the parts as equal as possible.
Quick example:
[3, 4, 4, 1, 2, 1]
might be splitted to [1, 4, 3] and [1, 2, 4]
and the sum difference will be 1
Now - if the parts can have arbitrary lengths, this is a variation of the Partition problem and we know that's it's weakly NP-Complete.
But does the restriction about splitting the list into equal parts (let's say it's always
k
and2k
) make this problem solvable in polynomial time? Any proofs to that (or a proof scheme for the fact that it's stillNP
)?
It is still
NP
complete. Proof by reduction ofPP
(your full variation of the Partition problem) toQPP
(equal parts partition problem):Take an arbitrary list of length
k
plus additionalk
elements all valued as zero.We need to find the best performing partition in terms of
PP
. Let us find one using an algorithm forQPP
and forget about all the additionalk
zero elements. Shifting zeroes around cannot affect this or any competing partition, so this is still one of the best performing unrestricted partitions of the arbitrary list of lengthk
.