ABSTRACT
The purposes of complexity theory are to ascertain the amount of computational resources required to solve important computational problems, and to classify problems according to their difficulty. The resourcemost often discussed is computational time, althoughmemory (space) and circuitry (or hardware) have also been studied. Themain challenge of the theory is to prove lower bounds, i.e., that certain problems cannot be solvedwithout expending large amounts of resources. Although it is easy to prove that inherently difficult problems exist, it has turned out to be much more difficult to prove that any interesting problemsarehard to solve.Therehasbeenmuchmore success inproviding strong evidence of intractability, basedonplausible,widely held conjectures. In both cases, themathematical arguments of intractability rely on the notions of reducibility and completeness-which are the topics of Chapter 23. Before one can understand reducibility and completeness, however, one must grasp the notion of a complexity class-and that is the topic of this chapter. First, however, we want to demonstrate that complexity theory really can prove-to even the
most skeptical practitioner-that it is hopeless to try to build hardware or programs that solve certain problems. As our example, we consider the manufacture and testing of logic circuits and communication protocols.Many problems in these domains are solved by building a logical formula over a certain vocabulary, and then determining whether the formula is logically valid, or whether counterexamples (i.e., bugs) exist. The choice of vocabulary for the logic is important here, as the next paragraph illustrates.
