Document Summary:

These are the lecture notes from a graduate course on Computational Complexity taught at the University of Washington. This topic fits in the middle of three of the fundamental areas of the Theory of Computation, which can be summarized with respect to their approaches to computational problems as follows:

- Computability: Determine whether an algorithm exist that solves a given problem.

- Computational Complexity: For those problems that are computable, determine a coarse analysis of their time and space requirements. Such analyses may well ignore the differences between polynomials, and concentrate on the difference between polynomial and exponential behavior.

- Analysis of Algorithms: For those problems that can be solved in polynomial time, determine a more exact analysis of their time and space requirements.

This text adopts some approaches that will appear unconventional. For example, alternating Turing machines are introduced very early, and deterministic and nondeterministic Turing machines treated as special cases. This simplifies many proofs, such as that of Savitch's Theorem, the P-completeness of the circuit value problem, the NP-completeness of the satisfiability problem, and the PSPACE-completeness of the quantified Boolean formula problem.

Another unconventional approach is to use log space reducibility rather than polynomial time reducibility when reducibility is first introduced in Chapter 5, and to begin with NL-completeness rather than the more important NP-completeness. The reason for this decision is twofold. First, the generic reduction in proving the NL-completeness of the directed graph connectivity problem is much simpler than the generic reduction normally used to prove the NP-completeness of the satisfiability problem, and thus gives the student a good "warmup" for the more important completeness proofs to come. Second, the NP-completeness proof of the satisfiability problem given in Theorem 8.7 is greatly simplified by the machinery built up in Chapter 7 on P-complete problems.