Complexity Classes - Models of Computation: Exploring the Power of Computing - page 327

CHAPTER
Complexity Classes
In an ideal world, each computational problem would be classified at least approximately by its
use of computational resources. Unfortunately, our ability to so classify some important prob-
lems is limited. We must be content to show that such problems fall into general complexity
classes, such as the polynomial-time problems P , problems whose running time on a determin-
istic Turing machine is a polynomial in the length of its input, or NP , the polynomial-time
problems on nondeterministic Turing machines.
Many complexity classes contain “complete problems,” problems that are hardest in the
class. If the complexity of one complete problem is known, that of all complete problems is
known. Thus, it is very useful to know that a problem is complete for a particular complexity
class. For example, the class of NP -complete problems, the hardest problems in NP ,contains
many hundreds of important combinatorial problems such as the Traveling Salesperson Prob-
lem. It is known that each NP -complete problem can be solved in time exponential in the size
of the problem, but it is not known whether they can be solved in polynomial time. Whether
P and NP are equal or not is known as the P = NP question. Decades of research have been
devoted to this question without success. As a consequence, knowing that a problem is NP -
complete is good evidence that it is an exponential-time problem. On the other hand, if one
such problem were shown to be in P , all such problems would be been shown to be in P ,a
result that would be most important.
In this chapter we classify problems by the resources they use on serial and parallel ma-
chines. The serial models are the Turing and random-access machines. The parallel models
are the circuit and the parallel random-access machine (PRAM). We begin with a discussion
of tasks, machine models, and resource measures, after which we examine serial complexity
classes and relationships among them. Complete problems are defined and the P -complete,
NP -complete, and PSPACE -complete problems are examined. We then turn to the PRAM
and circuit models and conclude by identifying important circuit complexity classes such as
NC and P/poly .
327