Unfortunately for computer scientists and computer users, many hundreds of very interesting application problems are NP-complete. What can be done if a problem that needs a solution is NP-complete? A variety of solutions is possible. Although it may be the case that no polynomially bounded algorithm is known to exist, there still could be significant differences in the complexities of known algorithms--as always, we should strive to pick the most efficient one possible. It is also possible to look at the average performance of algorithms rather than at their worst-case performance, and try to decide which one is best--it is quite possible that an algorithm for an NP-complete problem will take exponential time in the worst case, but will only take polynomial time in the average case. We may also decide to study the range of likely inputs based on empirical studies, and find out which...