Java Reference
In-Depth Information
Coping with NP -Complete Problems
17.2.3
Finding that your problem is NP-complete might not mean that you can just forget
about it. Traveling salesmen need to find reasonable sales routes regardless of the
complexity of the problem. What do you do when faced with an NP-complete
problem that you must solve?
There are several techniques to try. One approach is to run only small instances
of the problem. For some problems, this is not acceptable. For example, TRAVEL-
ING SALESMAN grows so quickly that it cannot be run on modern computers for
problem sizes much over 30 cities, which is not an unreasonable problem size for
real-life situations. However, some other problems in NP, while requiring expo-
nential time, still grow slowly enough that they allow solutions for problems of a
useful size.
Consider the Knapsack problem from Section 16.1.1. We have a dynamic pro-
gramming algorithm whose cost is (nK) for n objects being fit into a knapsack of
size K. But it turns out that Knapsack is NP-complete. Isn't this a contradiction?
Not when we consider the relationship between n and K. How big is K? Input size
is typically O(n lg K) because the item sizes are smaller than K. Thus, (nK) is
exponential on input size.
This dynamic programming algorithm is tractable if the numbers are “reason-
able.” That is, we can successfully find solutions to the problem when nK is in
the thousands. Such an algorithm is called a pseudo-polynomial time algorithm.
This is different from TRAVELING SALESMAN which cannot possibly be solved
when n = 100 given current algorithms.
A second approach to handling NP-complete problems is to solve a special
instance of the problem that is not so hard. For example, many problems on graphs
are NP-complete, but the same problem on certain restricted types of graphs is
not as difficult. For example, while the VERTEX COVER and K-CLIQUE prob-
lems are NP-complete in general, there are polynomial time solutions for bipar-
tite graphs (i.e., graphs whose vertices can be separated into two subsets such
that no pair of vertices within one of the subsets has an edge between them). 2-
SATISFIABILITY (where every clause in a Boolean expression has at most two
literals) has a polynomial time solution. Several geometric problems require only
polynomial time in two dimensions, but are NP-complete in three dimensions or
more. KNAPSACK is considered to run in polynomial time if the numbers (and
K) are “small.” Small here means that they are polynomial on n, the number of
items.
In general, if we want to guarantee that we get the correct answer for an NP-
complete problem, we potentially need to examine all of the (exponential number
of) possible solutions. However, with some organization, we might be able to either
examine them quickly, or avoid examining a great many of the possible answers
in some cases.
For example, Dynamic Programming (Section 16.1) attempts to
Search WWH ::




Custom Search