Table of contents - Classifying the Computational Complexity of Problems

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. D^p

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