Encyclopedia > Subset sum problem

  Article Content

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.



All Wikipedia text is available under the terms of the GNU Free Documentation License

 
  Search Encyclopedia

Search over one million articles, find something about almost anything!
 
 
  
  Featured Article
East Farmingdale, New York

... 45 to 64, and 10.6% who are 65 years of age or older. The median age is 34 years. For every 100 females there are 102.8 males. For every 100 females age 18 and over, ...

 
 
 
This page was created in 34.1 ms