Is thinking computable--not just in principle, but in practice? In the past this was the subject of vigorous exchanges between philosophers [1,2,3]; today, with the promise of artificial intelligence (AI) appearing ever brighter--in what is arguably its third or fourth incarnation--this is a question that naturally interests many scientists working in the area of computing, as well as those in cognitive sciences.

The issue of tractability, that is, whether a problem that can be solved by algorithmic means may nevertheless remain open on account of the impractical resources required for its resolution, has indeed interested not just AI researchers but even those who are concerned exclusively with human reasoning ability. For instance, while mainstream economics views rational agents having access to complete information about a situation to be capable of arriving at the optimal strategy, it has been pointed out that the prohibitive cost of computing such a solution can force Homo economicus to be a “satisficing” rather than a “maximizing” creature [4].

As the book points out, a similar viewpoint in cognitive science holds that humans can solve only those problems that can be computed in polynomial time [5]. This framework, which the authors call the P-cognition thesis, may be overly pessimistic about human cognitive capabilities because, in reality, several problems that are “hard” when looked at from this lens are handled fairly well in the course of our regular activities.

As the book points out, this could be because a problem that may be difficult to solve in its most general form may nevertheless be tractable in practice when one or more parameters characterizing it are subjected to constraints (termed as the fixed-parameter tractable or FPT-cognition thesis). While the main focus of the book is a detailed exposition of this framework, which it illustrates by dwelling in detail on three mental processes (namely coherence, analogy, and communication), it views itself more broadly as an introduction to using computational complexity to analyze computational-level theories of cognitive phenomena (that is, the highest level of explanation in the Marr hierarchy [6] that focuses on the goals and logic rather than the algorithm or the details of implementation).

Following the introduction, the first three chapters provide readers with an introduction to computational complexity theory. By necessity, this is rather brief and describes in detail only the distinction between P and NP. However, for those encountering the subject for the first time, the book provides several practice problems and exercises to familiarize the reader with the requisite technical tools. Following this, the next three chapters move on to the principal focus of the book, that is, fixed-parameter tractability and the parameterized complexity classes.

It appears that the concept of parameterized complexity has an intimate connection to work on phase transitions in the computational complexity of a problem as a parameter characterizing its “hardness” is altered (for example, see [7]). Both of these concepts stem from the realization that, while a problem may be intractable in terms of its “worst case” examples, the average case may be relatively easy to solve. However, the authors seem to be unaware of such connections with areas outside their immediate areas of specialization. This is also reflected in chapter 10’s discussion of the specific cognitive process of coherence, that is, whether it is possible to find truth assignments for a set of beliefs so as to satisfy as many constraints relating to these beliefs as possible. This is identical to the problem of finding the global minimum of a rugged energy landscape, which has applications to problems as diverse as the traveling salesman and protein folding [8]. However, the authors do not make this connection. Similarly, the more restricted problem of consistent coherence, where one asks whether a truth assignment that satisfies all constraints is possible, is equivalent to asking if the corresponding belief network is structurally balanced [9]. This provides a connection between the contents of the book and an exciting topic in the area of complex networks, which the authors may want to point out in a future edition. Another example is the chapter that considers the complexity of analogy derivation (viewed as structure mapping), where much of the extensive prior literature relevant to this problem, such as the work of Hofstadter’s group [10], is not discussed or cited.

The next chapter covers one of the book’s most exciting topics: human communication as a computational problem involving Bayesian inference; however, the discussion is extremely brief.Moreover, readers unfamiliar with Bayesian networks may find this chapter very hard to follow. I wish the book had treated these cognitive processes (considered in chapters 10 through 12) in greater depth and had moved the discussion about the common objections to a computational view of cognitive processes (chapter 9) to an appendix. I also found several errors, reflecting a lack of copy editing; this detracts from its value as a textbook for readers unfamiliar with the topics treated. However, on the whole, these problems do not seriously detract from the strong points of the book, which will fill an obvious need in the literature for a text that introduces the reader to this important topic.