Subset sum problem

The subset sum problem is an important problem in complexity theory and cryptography. The problem is this: given a set of integers, does any subset sum to 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, and is perhaps the simplest such problem to describe.

An equivalent problem is this: given a set of integers and an integer s, does any subset sum to s? Subset sum can also be thought of as a special case of the knapsack problem.

Although the problem was described above in terms of integers and addition, it can actually be defined using any group. For example, the problem could be: given an integer n and a set of integers in the range [0,n-1], does any subset sum to zero modulo n? This form of the problem has been used as a basis for several public key cryptography systems. However, most of them have been broken, reducing confidence in those still unbroken. For some reason, it is traditional in cryptography to say "knapsack problem" when it is actually the subset sum problem that is meant.

No algorithm is known for which we can prove that it solves subset sum in polynomial time. If any such algorithms exist, then some of them are already known. See the bottom of the Complexity_classes_P_and_NP for one such algorithm.