|
Figure 11-5. Encoding the clause (A or not B) using a clause node (highlighted), and adding detours requiring A to be
true (left to right) and B to be false (right to left) in order to satisfy the clause (that is, visit the node)
Chapter 11
■
hard problems and (lImIted) sloppIness
239
A Ménagerie of Monsters
In this section, I’ll give you a brief glimpse of a few of the thousands of known NP-complete problems. Note that the
descriptions here serve two purposes at once. The first, and most obvious, purpose is to give you an overview of lots
of hard problems so that you can more easily recognize (and prove) hardness in whatever problems you may come
across in your programming. I could have given you that overview by simply listing (and briefly describing) the
problems. However, I’d also like to give you some examples of how hardness proofs work, so I’m going to describe the
relevant reductions throughout this section.
Return of the Knapsack
The problems in this section are mostly about selecting subsets. This is a kind of problem you can encounter in many
settings. Perhaps you’re trying to choose which projects to finish within a certain budget? Or pack different-sized
boxes into as few trucks as possible? Or perhaps you’re trying to fill a fixed set of trucks with a set of boxes that will give
you as much profit as possible? Luckily, many of these problems have rather efficient solutions in practice (such as the
pseudopolynomial solutions to the knapsack problems in Chapter 8 and the approximations discussed later in this
chapter), but if you want a polynomial algorithm, you’re probably out of luck.
9
Note
■
pseudopolynomial solutions are known for only some np-hard problems. In fact, for many np-hard problems,
you can’t find a pseudopolynomial solution unless p = np. Garey and Johnson call these NP-complete in the strong sense.
(For more details, see section 4.2 in their book, Computers and Intractability.)
The knapsack problem should be familiar by now. I discussed it with a focus on the fractional version in
Chapter 7, and in Chapter 8 we constructed a pseudopolynomial solution using dynamic programming. In this
section, I’ll have a look at both the knapsack problem itself and a few of its friends.
Let’s start with something seemingly simple,
10
the so-called partition problem. It’s really innocent-looking—it’s
just about equitable distribution. In its simplest form, the partition problem asks you to take a list of numbers
(integers, say) and partition it into two lists with equal sums. Reducing SAT to the partition problem is a bit involved,
so I’m just going to ask you to trust me on this one (or, rather, see the explanation of Garey and Johnson, for example).
Moving from the partition problem to others is easier, though. Because there’s seemingly so little complexity
involved, using other problems to simulate the partition problem can be quite easy. Take the problem of bin packing,
for example. Here we have a set of items with sizes in the range from 0 to k, and we want to pack them into bins of
size k. Reducing from the partition problem is quite easy: We just set k to half the sum of the numbers. Now if the bin
packing problem manages to cram the numbers into two bins, the answer to the partition problem is yes; otherwise,
the answer is no. This means that the bin packing problem is NP-hard.
Another well-known problem that is simple to state is the so-called subset sum problem. Here you once again
have a set of numbers, and you want to find a subset that sums to some given constant, k. Once again, finding a
reduction is easy enough. For example, we can reduce from the partition problem, by (once again) setting k to half the
sum of the numbers. A version of the subset sum problem locks k to zero—the problem is still NP-complete, though
(Exercise 11-4).
9
Both for this section and the following two, you might want to try to show that the examples in the initial paragraphs are,
in fact, NP-hard.
10
To make it easier to follow the arguments in these sections, I’ll generally progress (using reductions) from seemingly simple
problems to more expressive ones. In reality, of course, they’re all just as expressive (and hard)—but some problems hide this better
than others.
Chapter 11
■
hard problems and (lImIted) sloppIness
240
Now, let’s look at the actual (integral, nonfractional) knapsack problem. Let’s deal with the 0-1 version first.
We can reduce from the partition problem again, if we want, but I think it’s easier to reduce from subset sum.
The knapsack problem can also be formulated as a decision problem, but let’s say we’re working with the same
optimization version we’ve seen before: We want to maximize the sum of item values, while keeping the sum of item
sizes below our capacity. Let each item be one of the numbers from the subset sum problem, and let both value and
weight be equal to that number.
Now, the best possible answer we could get would be one where we match the knapsack capacity exactly. Just
set the capacity to k, and the knapsack problem will give us the answer we seek: Whether we can fill up the knapsack
completely is equivalent to whether we can find a sum of k.
To round up this section, I’ll just briefly touch upon one of the most obviously expressive problems out there:
Do'stlaringiz bilan baham: |
