Table of Contents
Classifying the Computational Complexity of Problems

1. Introduction
2. Definitions
2.1. Decision problems and encodings
2.2. Turing machines and complexity classes
2.3. Other models of computation
2.4. Efficient reducibility
3. Consequences of Efficient Reducibility
3.1. A complete problem represents a class
3.2. Lower bounds on computational complexity
3.3. Speed-up
4. Complete Problems in Four Important Complexity Classes
4.1. NLOG-complete problems
4.2. P-complete problems
4.3. NP-complete problems
4.4. PSPACE-complete problems
5. Other Classes
5.1. Alternation and the polynomial-time hierarchy
5.2. Probabilistic classes
5.3. Parallel computation
5.4. #P
5.5. Dp
6. Complexities of Specific Problems
6.1. Logic
6.2. Games
6.3. Algebraic word problems
6.4. Formal language theory
7. Related Issues
7.1. Relativization
7.2. Structural issues
7.3. Languages which capture complexity classes
7.4. Complexity of finite problems
8. Conclusion
1