Problem 19 Answer: "Rating Trading, Part 2"

We prove the problem NP-complete by reduction to the subset-sum problem.

Given an instance of the subset-sum problem, where we have a set A1 ... An, and we want to determine if there is a subset that sums to exactly B.

Let X be the sum A1 + ... + An. (Assume that B <= X; otherwise the problem is trivial.) Consider an instance of the Generalized Math Trade Problem with two participants P and Q. Person P has objects which he values at (2*A1) ... (2*An) and person Q values at (A1 ... An) respectively. Person Q has one object which he values at B and P values at 3X. Choose a target value of 5X-B. The only way to achieve the target value under the constraints is for Q to give P his object, and P to give Q objects from his set that Q values at a total of exactly B. Thus if we had a way to determine whether this was possible, we would have solved the subset-sum problem.