Java Reference
In-Depth Information
Exponential time problems
TOH
NP problems
NP−complete problems
TRAVELING SALESMAN
P problems
SORTING
Figure17.5
Our knowledge regarding the world of problems requiring expo-
nential time or less. Some of these problems are solvable in polynomial time by a
non-deterministic computer. Of these, some are known to be NP-complete, and
some are known to be solvable in polynomial time on a regular computer.
lem that is NP-complete, then a polynomial solution can be found for all such
problems. The implication is that,
1. Because no one has yet found such a solution, it must be difficult or impos-
sible to do; and
2. Effort to find a polynomial time solution for one NP-complete problem can
be considered to have been expended for all NP-complete problems.
How is NP-completeness of practical significance for typical programmers?
Well, if your boss demands that you provide a fast algorithm to solve a problem,
she will not be happy if you come back saying that the best you could do was
an exponential time algorithm. But, if you can prove that the problem is NP-
complete, while she still won't be happy, at least she should not be mad at you! By
showing that her problem is NP-complete, you are in effect saying that the most
brilliant computer scientists for the last 50 years have been trying and failing to find
a polynomial time algorithm for her problem.
Problems that are solvable in polynomial time on a regular computer are said
to be in class P. Clearly, all problems in P are solvable in polynomial time on
a non-deterministic computer simply by neglecting to use the non-deterministic
capability. Some problems inNP areNP-complete. We can consider all problems
solvable in exponential time or better as an even bigger class of problems because
all problems solvable in polynomial time are solvable in exponential time. Thus, we
can view the world of exponential-time-or-better problems in terms of Figure 17.5.
The most important unanswered question in theoretical computer science is
whether P = NP. If they are equal, then there is a polynomial time algorithm
