Java Reference
In-Depth Information
exponential-time program with cost 1:001
n
is practical. But the reality is that we
know of almost no problems where the best polynomial-time algorithm has high
degree (they nearly all have degree four or less), while almost no exponential-time
algorithms (whose cost is (O(c
n
)) have their constant c close to one. So there is not
much gray area between polynomial and exponential time algorithms in practice.
For the rest of this chapter, we define a hard algorithm to be one that runs in
exponential time, that is, in (c
n
) for some constant c > 1. A definition for a hard
problem will be presented in the next section.
The Theory of
NP
-Completeness
17.2.1
Imagine a magical computer that works by guessing the correct solution from
among all of the possible solutions to a problem. Another way to look at this is
to imagine a super parallel computer that could test all possible solutions simul-
taneously. Certainly this magical (or highly parallel) computer can do anything a
normal computer can do. It might also solve some problems more quickly than a
normal computer can. Consider some problem where, given a guess for a solution,
checking the solution to see if it is correct can be done in polynomial time. Even
if the number of possible solutions is exponential, any given guess can be checked
in polynomial time (equivalently, all possible solutions are checked simultaneously
in polynomial time), and thus the problem can be solved in polynomial time by our
hypothetical magical computer. Another view of this concept is this: If you cannot
get the answer to a problem in polynomial time by guessing the right answer and
then checking it, then you cannot do it in polynomial time in any other way.
The idea of “guessing” the right answer to a problem — or checking all possible
solutions in parallel to determine which is correct — is called non-determinism.
An algorithm that works in this manner is called a non-deterministic algorithm,
and any problem with an algorithm that runs on a non-deterministic machine in
polynomial time is given a special name: It is said to be a problem in NP. Thus,
problems in NP are those problems that can be solved in polynomial time on a
non-deterministic machine.
Not all problems requiring exponential time on a regular computer are in NP.
For example, Towers of Hanoi is not in NP, because it must print out O(2
n
) moves
for n disks. A non-deterministic machine cannot “guess” and print the correct
answer in less time.
On the other hand, consider the TRAVELING SALESMAN problem.
TRAVELING SALESMAN (1)
Input: A complete, directed graph G with positive distances assigned to
each edge in the graph.
Output: The shortest simple cycle that includes every vertex.
