3
$\begingroup$

Suppose we have a set $D$ of denominations of coins and a our input is a "tip jar" containing some finite number of these coins (e.g., five nickels, a dime and three quarters). In the first two problems, we want to know whether it is possible to divide the money in the jar equally between two people; in the third one, we're satisfied if the money can be divided almost equally. What is the complexity of these problems?

  1. $D = \{1, 2, 4, 8, \dots\}$.

  2. $D = \{1, 2, 3, 4, \dots\}$.

  3. $D = \{1, 2, 3, 4, \dots\}$ but we only require the two people to be given amounts $x$ and $y$, respectively, satisfying $|x-y|< 10$.

My main question is what sets $D$ lead to the problem being in P and what makes it NP-complete.

$\endgroup$
1
$\begingroup$

Problem 2 is the same as the NP-complete problem PARTITION. Problem 3 is also NP-complete, since we can always arrange all denominations to be multiples of 10 cents.

The most interesting case is Problem 1. If the jar contains in total $2S$ cents, then we are looking for a subset of the jar summing to $S$. If $S$ is odd then there is no solution unless the jar contains a 1 cent coin, in which case we take one such coin and put it aside (it forms part of the solution), and update the target sum to $S-1$. Is $S$ is even we do nothing. In both cases, the new target sum is even. The number of 1 cent coins which appear in a solution must be even, and so we can group the 1 cent coins in pairs, replacing them with 2 cent coins (if there is an odd number, we just throws the odd one out). Now we repeat the same procedure with the 2 cent coins, the 4 cent coins, and so on, until we either reach the target sum or find out that the target sum is not reachable. This algorithm runs in polynomial time.

$\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.