Question

Anybody understands NP complete problems? Especially the ones related to Bonnie and Clyde?

Answer 1

I don't know about the Bonnie and Clyde problem, but I do understand NP complete problems.

Answer 2

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 prove that the problem is in P, 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.

There are n checks as in part (3), but this time they are willing to accept a split in which the
dierence is no larger than 100 dollars, i.e., neither of them gets more than 100 dollars more
than the other.

This is NP Complete but I can't prove it. can you help? thanks

Answer 3

What other NP Complete problems do you know?

Answer 4

well I know that this is the same as the set-partition problem if we remove the 100 difference margin. I found an answer online but I can't copy it since I cannot understand how to reduce this to the set-partition problem

Answer 5

Can you explain the set-partition problem?

Answer 6

yes. you basically have a set and you want to partition it into two disjoint subsets where the sum of all elements in one subset is half the sum of all elements in the original set.

Answer 7

Oh ok.

Answer 8

Well, do you understand how to use that problem to solve the Bonnie and Clyde problem?

Answer 9

Yes, no?

Answer 10

no

Answer 11

I mean I do know how to do it with the normal problem without the 100 difference margin

Answer 12

If Bonnie and Clyde have to split it evenly then we immediately have a set-partition problem

Answer 13

Consider if the took out an item under 100 and then tried to set partition.

Answer 14

ok

Answer 15

you have to play around with the problem in this fashion.

Answer 16

I am still confused. Thanks but I give up. there is a solution where they multiply things by 1000 but I have no idea as of what's the motivation behind that multiplication

Answer 17

1000? And the margin is 100?

Answer 18

yea. here is the link: http://www.cs.ucdavis.edu/~amenta/w04/dis7.pdf

Answer 19

it's the last problem on that link

Answer 20

It looks like they use Set Partition to get the closest possible solution.

Answer 21

Yea man lol. I am just not good at this stuff. Thanks anyways.

Answer 22

I have another idea for a solution.

Answer 23

```
for x in range(100):
S = moneybag.copy().add(x)
if set-partition(S):
return true
return false
```

Answer 24

Perhaps make that `range 101`. We want `x` to be from `0` to `100`.

Answer 25

Since this will run set-partition a constant number of times, we are showing that the problem is as easy as set-partition.

Answer 26

sweet. thanks

Answer 27

Do you understand it?

Answer 28

yea. I was thinking about that too but wasn't sure if splitting an additional check would compensate for the difference

Answer 29

If there is a solution that is \(x\leq100\) different, then by adding in \(x\) to the bag, there will be a completely even solution.

Answer 30

This works when `1` is the lowest denomination. If there are cents involved, then we would use `x in range(0, 100*100+1, 0.01)`. So long as there is a minimum denomination, this works.

Answer 31

And if there is no solution, then adding in \(x\) simply will not create a solution.