Chapter11
Limitations
of Algorithm Power
Intellect distinguishes between the possible and the impossible;
reason distinguishes between the sensible and the senseless. Even the possible
can be senseless.
—Max
Born (1882–1970), My Life and My Views,
1968
In the preceding chapters of this book, we encountered dozens of algorithms for solving a variety of different problems. A fair assessment of algorithms as problem-solving tools is inescapable: they are very powerful instruments, espe-cially when they are executed by modern computers. But the power of algorithms is not unlimited, and its limits are the subject of this chapter. As we shall see, some problems cannot be solved by any algorithm. Other problems can be solved algo-rithmically but not in polynomial time. And even when a problem can be solved in polynomial time by some algorithms, there are usually lower bounds on their efficiency.
We start, in Section 11.1,
with methods for obtaining lower bounds, which are estimates on a minimum
amount of work needed to solve a problem. In general, obtaining a nontrivial
lower bound even for a simple-sounding problem is a very difficult task. As opposed
to ascertaining the efficiency of a particular algorithm, the task here is to
establish a limit on the efficiency of any
algorithm, known or unknown. This also necessitates a careful description of
the operations such algo-rithms are allowed to perform. If we fail to define
carefully the “rules of the game,” so to speak, our claims may end up in the
large dustbin of impossibility-related statements as, for example, the one made
by the celebrated British physicist Lord Kelvin in 1895: “Heavier-than-air
flying machines are impossible.”
Section 11.2 discusses
decision trees. This technique allows us, among other applications, to
establish lower bounds on the efficiency of comparison-based algorithms for
sorting and for searching in sorted arrays. As a result, we will be able to
answer such questions as whether it is possible to invent a faster sorting
algorithm than mergesort and whether binary search is the fastest algorithm for
searching in a sorted array. (What does your intuition tell you the answers to
these questions will turn out to be?) Incidentally, decision trees are also a
great vehicle for directing us to a solution of some puzzles, such as the
coin-weighing problem discussed in Section 4.4.
Section 11.3 deals with the
question of intractability: which problems can and cannot be solved in
polynomial time. This well-developed area of theoretical computer science is
called computational complexity theory. We present the basic elements of this
theory and discuss informally such fundamental notions as P , NP,
and NP-complete problems, including
the most important unresolved question of theoretical computer science about
the relationship between P and NP problems.
The last section of this
chapter deals with numerical analysis. This branch of computer science concerns
algorithms for solving problems of “continuous” mathematics—solving equations
and systems of equations, evaluating such func-tions as sin x and ln x, computing integrals, and so on. The nature of
such problems imposes two types of limitations. First, most cannot be solved
exactly. Second, solving them even approximately requires dealing with numbers
that can be rep-resented in a digital computer with only a limited level of
precision. Manipulating approximate numbers without proper care can lead to
very inaccurate results. We will see that even solving a basic quadratic
equation on a computer poses sig-nificant difficulties that require a
modification of the canonical formula for the equation’s roots.
Related Topics
Privacy Policy, Terms and Conditions, DMCA Policy and Compliant
Copyright © 2018-2024 BrainKart.com; All Rights Reserved. Developed by Therithal info, Chennai.