Java Reference
In-Depth Information
and translating it to written text is an example of a problem whose goals are easy
to define, but whose solution is not easy to discover. But even though a natural
language processing algorithm might be difficult to write, the program's running
time might be fairly fast. There are many practical systems today that solve aspects
of this problem in reasonable time.
None of these is what is commonly meant when a computer theoretician uses
the word “hard.” Throughout this section, “hard” means that the best-known alg-
orithm for the problem is expensive in its running time. One example of a hard
problem is Towers of Hanoi. It is easy to understand this problem and its solution.
It is also easy to write a program to solve this problem. But, it takes an extremely
long time to run for any “reasonably” large value of n. Try running a program to
solve Towers of Hanoi for only 30 disks!
The Towers of Hanoi problem takes exponential time, that is, its running time
is (2
n
). This is radically different from an algorithm that takes (n log n) time
or (n
2
) time. It is even radically different from a problem that takes (n
4
) time.
These are all examples of polynomial running time, because the exponents for all
terms of these equations are constants. Recall from Chapter 3 that if we buy a new
computer that runs twice as fast, the size of problem with complexity (n
4
) that
we can solve in a certain amount of time is increased by the fourth root of two.
In other words, there is a multiplicative factor increase, even if it is a rather small
one. This is true for any algorithm whose running time can be represented by a
polynomial.
Consider what happens if you buy a computer that is twice as fast and try to
solve a bigger Towers of Hanoi problem in a given amount of time. Because its
complexity is (2
n
), we can solve a problem only one disk bigger! There is no
multiplicative factor, and this is true for any exponential algorithm: A constant
factor increase in processing power results in only a fixed addition in problem-
solving power.
There are a number of other fundamental differences between polynomial run-
ning times and exponential running times that argues for treating them as quali-
tatively different. Polynomials are closed under composition and addition. Thus,
running polynomial-time programs in sequence, or having one program with poly-
nomial running time call another a polynomial number of times yields polynomial
time. Also, all computers known are polynomially related. That is, any program
that runs in polynomial time on any computer today, when transferred to any other
computer, will still run in polynomial time.
There is a practical reason for recognizing a distinction. In practice, most poly-
nomial time algorithms are “feasible” in that they can run reasonably large inputs
in reasonable time. In contrast, most algorithms requiring exponential time are
not practical to run even for fairly modest sizes of input. One could argue that
a program with high polynomial degree (such as n
100
) is not practical, while an
