This is the first book to provide an accessible introduction to computational complexity analysis and its application to questions of intractability in cognitive science. It is essential reading for students and researchers who want to understand how cognitive models can be scaled from the lab to situations of real-world complexity.