Wednesday, September 9, 2009

Wednesday Math, Vol. 87: Subset sum


Back in May of 2008, I discussed the idea of NP Complete, a famous collection of problems that are related to one another in tricky ways, where none of the problems has a good method that will solve every example of the problem in a reasonable amount of time. One of the easiest of the problems to state is subset sum.

In this instance, we have a collection of six numbers - 44, 98, 12, 68, 7 and 32 - and a target number 162. These numbers were chosen at random by rolling dice that produce numbers from 1 to 100, and the 162 is the sum of two numbers from 1 to 100. Is it possible to take some sub-collection of the six and get them to add up to 162? The problem is "solved" when you find the sub-collection (known in math as a subset) that works, or you state that there is no such subset for this particular collection and target number.

The correct answer in this case is no subset works. Let me go over the method I used to figure this out.

The sum of all combined in 261. Note that there is only one odd number, that being 7, and the target is even, so for our purposes, 7 can be removed from the list, and the new sum is 254.

If we take away the 98 from the sum, the rest of the even numbers add up to 156, which is less than the target, so 98 has to be a part of any set that adds up to 162. 162-98 = 64, so we have to find a combination of 12, 44, 68 and 32 that add up to 64, and no such combination exists. Note that if we were allowed to use multiple copies of numbers, 32+32 = 64, but the 32 is only on the list once, so I can only use one copy.

The method I used here solved this instance fairly quickly. Some instances are easy and some are hard. Only having six numbers on the list means there are 64 possible subsets and one of them is the empty set, so if I used brute force, I only have to check 63 combinations to see if the right answer is there. 64 is two to the sixth power, and the number of subsets doubles every time an extra number is added to the list. If the list had twenty numbers on it, checking every combination would entail looking at over a million subsets, and a thirty number list has over a billion subsets. With sets that big or bigger, a computer is usually be brought to bear on the task, and because the problem is hard, sometimes even a computer will take a very long time to find the correct answer.

Next week, I'll discuss the problem known as 3 SAT. It has nothing to do with the test that high school students have to take.

No comments: