Subset sum problem

 related topics {math, number, function} {village, small, smallsup}

In computer science, the subset sum problem is an important problem in complexity theory and cryptography. The problem is this: given a set of integers, does the sum of some non-empty subset equal exactly zero? For example, given the set { −7, −3, −2, 5, 8}, the answer is yes because the subset { −3, −2, 5} sums to zero. The problem is NP-complete.

An equivalent problem is this: given a set of integers and an integer s, does any non-empty subset sum to s? Subset sum can also be thought of as a special case of the knapsack problem. One interesting special case of subset sum is the partition problem, in which s is half of the sum of all elements in the set.

Contents

General discussion

The subset sum problem is a good introduction to the NP-complete class of problems. There are two reasons for this

Although the subset sum problem is a decision problem, the cases when an approximate solution is sufficient have also been studied, in the field of approximations algorithms; one algorithm for the approximate version of the subset sum problem is given below.

Complexity

The complexity (difficulty of solution) of subset sum can be viewed as depending on two parameters, N, the number of decision variables, and P, the precision of the problem (stated as the number of binary place values that it takes to state the problem). (Note: here the letters N and P mean something different than what they mean in the NP class of problems.)

The complexity of the best known algorithms is exponential in the smaller of the two parameters N and P. Thus, the problem is most difficult if N and P are of the same order. It only becomes easy if either N or P becomes very small.

If N (the number of variables) is small, then an exhaustive search for the solution is practical. If P (the number of place values) is a small fixed number, then there are dynamic programming algorithms that can solve it exactly.

What is happening is that the problem becomes seemingly non-exponential when it is practical to count the entire solution space. There are two ways to count the solution space in the subset sum problem. One is to count the number of ways the variables can be combined. There are 2N possible ways to combine the variables. However, with N = 10, there are only 1024 possible combinations to check. These can be counted easily with a branching search. The other way is to count all possible numerical values that the combinations can take. There are 2P possible numerical sums. However, with P = 5 there are only 32 possible numerical values that the combinations can take. These can be counted easily with a dynamic programming algorithm. When N = P and both are large, then there is no aspect of the solution space that can be counted easily.