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 problems 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 deterministic 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 Problem. 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 $\stackrel{?}{=}$ 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 machines. 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.