Information Technology Reference
In-Depth Information
Perhaps surprisingly, there are no known solutions to the
Traveling Salesperson Problem that are fundamentally more effi
cient. Some improvements can be made to the basic approach of
trying all possible routes through the various cities, but no solu
tions are known that require only one computer with reasonable or
even feasible times. (Mathematical aside: If one thinks of the
amount of time as a function that depends on the amount of data,
then no algorithms are known for which the time is bounded by a
polynomial! Such time functions grow much too fast to allow real
istic computation of results for anything but the smallest data sets.)
Class NP
Class P identifies problems that have feasible solutions when one computer is available.
With as many computers available as desired, could we find feasible solutions to other
problems as well?
As an example, consider the exhaustive listing and search solution to the Traveling
Salesperson Problem. In this approach, all possible paths are considered, and the short
est route selected. If this approach were tried with many different computers—one for
each route, each computer could compute the cost for a different path. Next, each com
puter could compare the cost for its route with costs of routes computed by neighboring
computers. When a computer discovers its route is more costly that another, it could
drop out of the conversation, leaving processing to computers with relatively lowcost
routes. This approach requires coordination and communication, and details are a bit
tricky. However, it turns out that identification of the shortest route can be done in
somewhat under
n
2
units of time.
In this approach, the overall amount of work exceeds what is needed with only one ma
chine, due to the overhead of communication among machines. Communication over
head is unnecessary when only one computer is working. However, when the overall
work is spread over many computers, the resulting processing may experience a speed
up in time.
This analysis motivates the definition that a problem is in Class NP if it has some solu
tion that requires no more than a polynomial number of steps, given enough computers.
For example, the Traveling Salesperson Problem is in Class NP. In addition, Class NP
contains all problems in Class P; if the problem can be done efficiently with one proces
sor, it certainly can be done efficiently with many processors. Just let one computer do
all the work, and let any other computers remain idle.
