Subset Sum Problem
Little Timmy's grandmother gave him 5 black stones and 4 gray stones and told him to find a group of black stones that weigh the same as a group of gray stones. If he can find these groups, he should put them on his window sill to bring calmness into his life. Otherwise, he'll have to fetch more stones. To do this, Timmy decides to ask his mom for a balance to undertake the task. Although he doesn't know this, the set of weights, in pounds, for each stone is the following:
Will Timmy find two groups of stones that weigh the same?
More generally, will this class of problems take polynomial-time , meaning that it is in , and can also be solved using non-deterministic polynomial-time , meaning that it is also in ; or can he solve it only using non-deterministic polynomial-time algorithms, meaning that it is only in ?
This section requires Javascript.
You are seeing this because something didn't load right. We suggest you, (a) try
refreshing the page, (b) enabling javascript if it is disabled on your browser and,
finally, (c)
loading the
non-javascript version of this page
. We're sorry about the hassle.
1 solution
Relevant wiki: P versus NP
Timmy can, in fact, find two groups of stones that weigh the same. The problem can be modeled by negating the gray stones, and finding a sum that adds up to 0. Although there are a few solutions, one of them is comprised of the black stones weighing 3, 5, and 5 pounds; and grey stones weighing 4 and 9 pounds. Both of the groups weigh 13 pounds. The Subset-Sum problem shown here is in only. In fact, it is NP-complete. This is asserted by observing that a naïve algorithm takes time exponential in in the worst case scenario: when every combination of stones has to be weighted against each other and a solution, or no solution, is found. The running time of this procedure ends up being , as there are subsets, and at most elements need to be summed up to assert whether the particular subset adds up to 0.