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.
| Table of contents |
|
2 The NP-complete conundrum 3 Generalisations 4 External link |
The subset sum problem is a good introduction to the NP-complete class of problems. There are three reasons for this
Here P is equivalent to the number of constraints on the problem. When
Also inherent in the Subset Problem is a concise exposition of the NP-complete conundrum. That is the conundrum of infeasible problems. Let's say you had a magical way of solving the problem in polynomial time. If you can deliver a feasible solution, then you can say "it doesn't matter how I did it, here is the solution and here is the proof that it is right (it adds up)". However, what if someone, without your knowledge, gives you an infeasible problem? Your magical solution algorithm can not deliver a feasible solution. It will either fail, go on for ever, or deliver a solution for which there is no proof of correctness and hence no one will believe you.
This means that if you actually wanted to solve real subset sum problems, you would have to come up with a polynomially sized algorithm for proving infeasibility for problems where P = N. Anything short of that is an evasion.
Most physical problems in life can be solved quite nicely with a +/- 1% error. Being asked to solve an N = 100 subset sum problem with a precision of +/-2−100 seems silly and irrelevant. However, what it does do is to state in numerical precision terms the logical complexity of the problem. The advantage of this is that it allows you to use the language of numerical analysis to address what is typically seen as a problem of logical analysis.
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.
An algorithm (exponential time) for solving the subset sum problemGeneral discussion
What makes the problem difficult is that the number of binary place values it takes to state the problem needs to be equal to the number of decision variables in the problem. Take N as the number of decision variables, and P as the precision of the problem (stated as the number of binary place values that it takes to state the problem)
the problem is underdetermined, and it is easy to find a solution that will fit. With
the problem is overdetermined, and the search space is so small, that it is again easy to find an N. The problem is only difficult when
Addressing any other state of the problem than P = N is effectively changing the subject.The NP-complete conundrum
Generalisations
External link