Algorithm - find the minimal subtraction between sum of two arrays?

This problem is basically the optimization problem for Partition Problem with an extra constraint of equal parts. I'll prove that adding this constraint doesn't make the problem easier.

This problem is basically the optimization problem for Partition Problem with an extra constraint of equal parts. I'll prove that adding this constraint doesn't make the problem easier. NP-Hardness proof: Assume there was an algorithm A that solves this problem in polynomial time, we can solve the Partition-Problem in polynomial time.

Partition(S): for I in range(|S|): S += {0} result S+(0,0,...,0) k times 0, one can directly prove NP-Hardness by reduction. Polynomial is trivial and correctness is very similar to the above partion's correctness proof: if there is a partition, adding 'balancing' zeros is possible; the other direction is simply trimming those zeros.

I believe you got the indentation wrong - why would you execute result P=NP then this problem is NP-Hard though I cannot recall which theorem, so I might be wrong. I am thankful for your comment anyway, your suggested reduction is much simpler approach. – amit Oct 2 '11 at 9:54 1 @jpalacek: I don't see the problem with amit's reduction (although yours is definitely simpler).

According to the Wikipedia page, polynomial-time Turing-reducibility of an NP-complete problem (such as Partition) to the target problem suffices to show that the target problem is NP-hard. Turing-reducibility allows a polynomial number of calls to the target problem. Many-one reductions (which allow only a single call to the target problem, at the end) are only needed for NP-completeness.

– j_random_hacker Oct 2 '11 at 18:27.

Just a comment. Through all this swapping you can basically arrange the contents of both arrays as you like. So it is unimportant in which array the values are at start.

Can't do it in my head but I'm pretty sure there is a constructive solution. I think if you sort them first and then deal them according to some rule. Something along the lines If value > 0 and if sum(a)>sum(b) then insert to a else into b.

I cant really gove you an answer,but what I can give you is a way to a solution, that is you have to find the anglde that you relate to or peaks your interest. A good paper is one that people get drawn into because it reaches them ln some way.As for me WW11 to me, I think of the holocaust and the effect it had on the survivors, their families and those who stood by and did nothing until it was too late.