文档介绍：Algorithms plexity
Herbert S. Wilf
University of Pennsylvania
Philadelphia, PA 19104-6395
Copyright Notice
Copyright 1994 by Herbert S. Wilf. This material may be reproduced for any educational purpose, multiple
copies may be made for classes, etc. Charges, if any, for reproduced copies must be just enough to recover
reasonable costs of reproduction. Reproduction mercial purposes is prohibited. This cover page must
be included in all distributed copies.
Edition, Summer, 1994
This edition of Algorithms plexity is available at the web site <.edu/ wilf>.
It may be taken at no charge by all interested persons. Comments and corrections are e, and should
be sent to ******@
Chapter 5: pleteness
Introduction
In the previous chapter we met putational problems for which fast algorithms have never been
found, but neither have such algorithms been proved to be unattainable. Those were the primality-testing
problem, for which the best-known algorithm is delicately poised on the brink of polynomial time, and the
integer-factoring problem, for which the known algorithms are in a more primitive condition.
In this chapter we will meet a large family of such problems (hundreds of them now!). This family is not
just a list of seemingly di
putational problems. It is in fact bound together by strong structural
ties. The collection of problems, called the plete problems, includes many well known and important
questions in discrete mathematics, such as the following.
The travelling salesman problem (‘TSP’): Given n points in the plane (‘cities’), and a distance
there a tour that visits all n of the cities, returns to its starting point, and has total length
D?
Graph coloring: Given a graph G andanintegerK. Can the vertices of G be properly colored in K or
fewer colors?
Independent set: Given a graph G and an integer (G) contain an independent set of K vertices?
Bin packing: Given a
nite set S of positive integers, and an