** Next:** A proposed public-key system
** Up:** Subset-Sum (Knapsack) problems and
** Previous:** Subset-Sum (Knapsack) problems and
** Contents**

##

Subset-sum problems are hard

A subset of the numbers

adds up to 5842. Spend a few minutes
trying to find such a subset. Whether you succeed or not, I hope
you are convinced the task is not trivial.

This is an example of a *subset-sum* problem. In general,
we are given natural numbers and a target number and
asked to find a
with

A seemingly simpler problem is the *subset-sum decision*
problem. For a given and , decide whether there is an
for which holds, without being required to identify such an .
However, it can be proved that the decision problem is just as difficult
as the subset-sum problem in this sense:

**Theorem 17**
*Suppose we had a method of solving the subset-sum decision
problem. Then we could solve a subset-sum problem using the assumed
method times.*
(the is not particularly important-- the
main thing is that the number of uses of the method is not too large.)

Proof: Begin by using the method to decide if
is a sum of the -- if not, we can stop immediately. Then
use the method to determine if holds for some
.
If the answer is yes, we ignore for the rest of the analysis. If
the answer is no, we know we must have . In this second case,
we continue by using the method to decide whether there is
with

A yes answer means we can assume , otherwise .

The idea of this proof is more important than
the specific result. We show that one problem is as difficult as another
by showing that a method of solving the supposedly easier problem can be
used to solve another problem. This involves constructing one or several
easier problems whose solution answers the hard problem. We saw another
example of this idea in our discussion of the Rabin encryption system
(section 3.3).

Using more elaborate versions of the techniques in
Theorem 17, it can be shown that a method of solving
the subset-sum decision problem could be used to solve many other problems,
including:

- Factoring
- The Travelling Salesman
Problem
- Any Integer Programming Problem
- The Satisfiability
Problem

Don't worry if you are not familiar with the details
of these problems. The important point is that they are all well-known
problems for which many people have been unable to find efficient solution methods, which makes it unlikely that there is a method which solves
all subset-sum decision problems efficiently (we will go into more detail
on this in section 5).

The discussion above makes it plausible that some subset-sum problems
are difficult. Further, there is some evidence that the ``typical''
subset-sum problem is not easy.
V. Chvatal^{3} has shown that if the and
are randomly chosen, then with high probablility (i) there will be no
for which holds (ii) certain simple ways of proving this will
not work.

#### Footnotes

- ...
V. Chvatal
^{3}
- ``Hard Knapsack Problems,''
*Operations Research*,
vol. 28, pp 1402-1411

** Next:** A proposed public-key system
** Up:** Subset-Sum (Knapsack) problems and
** Previous:** Subset-Sum (Knapsack) problems and
** Contents**
*Translated from LaTeX by Scott Sutherland *

2002-12-14