What should I know about the sizes and speeds of computers? - The Tao of Computing - page 152

With this in mind, it is common to define a problem to be in Class P if the problem has
some solution, where the number of steps to process n data items is (no more than)
some polynomial involving n . For example, the problem of searching a collection of
data to find a specified item is in Class P, since some solution (e.g., the linear search)
requires only n units of work, and n is a polynomial.

With this definition, one can be reasonably optimistic and decree that a problem has a
feasible solution if it is in Class P. Searching data is feasible by this definition, for ex
ample. Similarly, many common computing applications, including the storage and re
trieval of data, fall within the scope of this notion of feasibility. All of these common ex
amples support the idea that problems within Class P may be considered to have
practical solutions. Conversely, considering Table 6.2, it seems reasonably safe to con
clude that problems outside Class P could not be solved in any acceptable amount of
time. That is, if all solutions to a problem with n data items require more steps than can
be described by any polynomial, then the work for all solutions must be exponentials
(e.g., 2 n ) or factorials (e.g., n !) or worse.

Exhaustive Search: As a second example of how problems might
scale, consider the following:

The Traveling Salesperson Problem

A salesperson is responsible for visiting a number of cities. In order to complete
this task efficiently, the salesperson wants to find a route of minimal cost that
goes through each city exactly once before returning to the starting point.

As an example, the map in Figure 6.1 shows several cities in the Midwest, to
gether with the cost involved for flying from one city to another. Thus, the fig
ureshows that it costs $134 to fly from Des Moines to Chicago. On the other
hand, there are no direct flights between Des Moines and Grand Rapids.

Minneapolis

$566 Grand Rapids

$190

$453

Detroit

$124

$107

$437

$367

$134

Chicago

$342

Des Moines

$132

$88

$144

$117

$330

$49

Kansas City St. Louis Fares quoted February 25, 2003

(All fares are least expensive available,
non-stop, 3-week advance notice)

Figure 6.1
Airfares between selected cities in the Midwest.