Part I – Introduction
1 – Introduction
Part II – Concepts and Techniques
2 – Polynomial versus Exponential Time
3 – Polynomial-Time Reductions
4 – Classical Complexity Classes
5 – Fixed-Parameter Tractable Time
6 – Parameterized Reductions
7 – Parameterized Complexity Classes
Part III – Reflections and Elaborations
8 – Dealing with Intractability
9 – Replies to Common Objections
Part IV – Applications
10 – Coherence as Constraint Satisfaction
11 – Analogy as Structure Mapping
12 – Communication as Bayesian Inference
Appendices
Appendix A – Mathematical Background
Appendix B – List of Computational Problems
Appendix C – Compendium of Complexity Results
Cognition and Intractability 