Content

Frontmatter and Preface

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