Regarding Np-complete and polynomial time. I have no idea where to start. I do u

Question

Regarding Np-complete and polynomial time. I have no idea where to start. I do understand what polynomial time and NP-complete is.

Bonnie and Clyde have just robbed a bank. They have a bag of money and want to divide it up. For each of the following scenarios, either give a polynomial-time algorithm, or prove that the problem is NP-complete. The input in each case is a list of the n items in the bag, along with the value of each.

1. There are n coins, but only 2 different denominations: some coins are worth x dollars, and some are worth y dollars. They wish to divide the money exactly evenly.

2. There are n coins, with an arbitrary number of different denominations, but each denomination is a nonnegative integer power of 2, i.e., the possible denominations are 1 dollar, 2 dollars, 4 dollars, etc. They wish to divide the money exactly evenly.

3. There are n checks, which are, in an amazing coincidence, made out to "Bonnie or Clyde." They wish to divide the checks so that they each get the exact same amount of money.

4. There are n checks as in part (c), but this time they are willing to accept a split in which the difference is no larger than 100 dollars.

Explanation / Answer

(1)

Assume that there m coins worth x dollars, n-m coins worth y dollars.

Then the total amount is m*x+ (n-m)*y dollars, denoted as S. Thus each of them wants to take S/2dollars.

Note that Bonnie can either take 0 coin worth x dollars, or 1 coin worth x dollars, or 2 coins worth x dollars…, or at most m coins worth x dollars. Since there are only two , we can just check after Bonnie taking coins worth x dollars, if coins worthy dollars can make up the rest of the amount.

For example, if Bonnie takes no coins worth x dollars, then check if S/2 mod y and if S/(2*y) <=(n-m). If Bonnie takes 1 coin worth x dollars, then check if (S/2-x) mod y and if (S/2-x)/y <=(n-m). There are at most m+1 possibility to check, because Bonnie can take at most m coins. In each possibility, constant number of operations is needed, thus this isa polynomial algorithm.

(2)

Sort all the coins by decreasing order. Give Bonnie the largest coin, then give Clyde coins until Clyde has the same amount as Bonnie. This will always happen if the rest of money is no less than their difference, because the denominations of coins are powered 2. When they have the same amount, give Bonnie the largest coin in the remaining coins, repeat the above process until all coins are gone. If after giving Bonnie one coin C, the sum of remaining coins is less than C. Then we cannot find an evenly division. Otherwise, we can find an evenly division.

(3)

NP-Complete

This problem is actually partition problem.

First, given a division, summing up the checks given to Bonnie to see if the sum is S/2 verifies the solution.(S is the sum of amount of all checks) .Then, we reduce Subset-Sum problem to this problem.

Assume in Subset-Sum problem, we are given a set of numbers, denoted as P.

Let S’ be the sum of all numbers in P, and t be the target number.

Form the set P’=PU(S1-2t)P has a subset summing up to t, if and only if P’ can be partitioned into two sets with equal sum. The reduction is obviously polynomial. Since Subset-Sum problem is NP-Complete, thus the problem is also NP-Complete.

(4) NP-Complete

First, given a division, u just check whether the sum of checksgiven to Bonnie and Clyde have a difference less than 100.Polynomial time verifiable. Then reduce the problem in (c) which is known NP-Complete to this problem.

Without loss of generality, we assume that the basic unit of the money on the checks is 1 dollar. The problem in (c) is: given a setoff checks {C1,C2,C3}, decide whether they can be divided evenly. Then we construct the set of checks in problem (d) as{C1*1000,C2*1000,…..,Cn*1000}. The original set of checks can be divided evenly if and only if these multiplied checks can be divided evenly by allowing a difference no larger than 100.Thetransformation is apparently polynomial time.

Related Questions

Navigate

• Browse (All)
• Browse R
• Subjects

Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.