W
Chapter 14
An Overview of
Computational
Complexity
e now reconsider computational complexity, the study of the
efficiency of algorithms. Complexity, briefly mentioned in Chapter
11, complements computability by separating problems that can be
solved in practice from those that can be solved only in principle. In
studying complexity, it is necessary to ignore many details, such as
the particulars of hardware, software, data structures, and implementation, and
look at the common, fundamental issues. For this reason, we work mostly with
orders-of-magnitude expressions. But, as we will see, even such a very highlevel view yields very useful results.
Efficiency is measured by resource requirements, such as time and space, so
we can talk about time-complexity and space-complexity. Here we will limit
ourselves to time-complexity, which is a rough measure of the time taken by a
particular computation. There are many results for space-complexity as well, but
time-complexity is a little more accessible and, at the same time, more useful.
Computational complexity is an extensive topic, most of which is well
beyond the scope of this text. There are some results, however, that are simply
stated and easily appreciated, and that throw further light on the nature of
languages and computation. In this chapter, we present a brief overview of the
most salient results in complexity. Many proofs are difficult and we will
dispense with them by reference to appropriate sources. Our intent here is to
present the flavor of the subject matter without getting bogged down in the
details. For this reason, we will allow ourselves a great deal of latitude, both in
the selection of topics and in the formality of the discussion.
Chapter 14
An Overview of
Computational
Complexity
e now reconsider computational complexity, the study of the
efficiency of algorithms. Complexity, briefly mentioned in Chapter
11, complements computability by separating problems that can be
solved in practice from those that can be solved only in principle. In
studying complexity, it is necessary to ignore many details, such as
the particulars of hardware, software, data structures, and implementation, and
look at the common, fundamental issues. For this reason, we work mostly with
orders-of-magnitude expressions. But, as we will see, even such a very highlevel view yields very useful results.
Efficiency is measured by resource requirements, such as time and space, so
we can talk about time-complexity and space-complexity. Here we will limit
ourselves to time-complexity, which is a rough measure of the time taken by a
particular computation. There are many results for space-complexity as well, but
time-complexity is a little more accessible and, at the same time, more useful.
Computational complexity is an extensive topic, most of which is well
beyond the scope of this text. There are some results, however, that are simply
stated and easily appreciated, and that throw further light on the nature of
languages and computation. In this chapter, we present a brief overview of the
most salient results in complexity. Many proofs are difficult and we will
dispense with them by reference to appropriate sources. Our intent here is to
present the flavor of the subject matter without getting bogged down in the
details. For this reason, we will allow ourselves a great deal of latitude, both in
the selection of topics and in the formality of the discussion.