Reviewed by
Gabriel Istrate
e-Austria Research Institute, Timisoara, Romania
Many social scientists (and, I would guess, a large fraction of the JASSS readership) have a somewhat uneasy relationship
with Computational Complexity. On one hand they are probably aware that this field has SOME implications for
their work (since, naturally, agents' capabilities are subject to natural computational constraints). On the other hand
they are put off by the mathematically heavy, rather esoteric assortment of notions and complexity classes (aptly
described as "the complexity zoo"[1]). Thus a book such as this one, that promises "a conceptual perspctive" on Computational Complexity is potentially of interest to the audience of this journal. Does it really deliver, though, on its promises?
First, let me qualify my answer. I am a theoretical computer scientist, a member of the (still small) community that can fully appreciate the technical aspects of Computational Complexity and is, at the same time, interested in Social Simulation and related problems (e.g. methodological issues in the Social Sciences). I view the book as a highly competent work, by one of the leading Theoretical Computer Scientists. I have enjoyed it and used selected portions of it in coursework, as an introduction to Computational Complexity. The "Conceptual Approach" in the book title reflects a war currently taking place in the Theoretical Computer Science community, roughly between "conceptualists" and "technical people" (those that emphasize mathematical difficulty and sophistication). The author is a (highly opinionated) member of the first camp (a camp I belong to as well), hence the title and approach of this book.
Computational Complexity is an attempt, not unlike Zoology, to classify computational problems (usually defined as infinite sets of questions with a YES/NO answer) into "families". Perhaps the fundamental concepts of the theory are complexity classes and reductions. Complexity classes represent the natural "families" of problems, usually defined by a type of computational device that can decide the problems in that class. For instance when the device is a deterministic Turing machine running in polynomial time the corresponding class of problems is denoted P. If the machine still runs in polynomial time but is allowed to make nondeterministic guesses we get the so-called class NP (for nondeterministic polynomial time). Whether these two classes are distinct is, of course, a famous open problem. The second concept, that of reduction, classifies the complexity of a problem in a more indirect manner. By reductions we generally map instances of a problem A to instances of a second problem B, in such a way that an efficient algorithm for solving B would yield an efficient method for solving problem A. There are many versions of this idea, yielding in some cases quite interesting computational models (machines with "oracles"). Some important complexity classes (e.g. the so-called Polynomial Hierarchy) can be defined using these tools. The notion of "complete" problems provides an indirect notion of a "hardest" problem in a complexity class. A fundamental insight of Levin, Cook and Karp was that such complete problems indeed exist.
The above-mentioned concepts are in a sense "classical", having been developed in the 70's and early 80's. The field experienced tremendous growth in the past 20 years (it has a dedicated annual conference with a 24-year history, and it has a central place in the main conferences in Theoretical Computer Science), with many exciting results that have transformed it into a mainstream area of Mathematics (see for instance Gowers et al. 2009).
The book attempts "to show that Computational Complexity is extremely rich in conceptual content and that this content should be explicitly communicated in expositions and courses on this subject". It also aims to provide a textbook illustrating this idea. Consequently it is many things in one: first and foremost, it is a (reasonably comprehensive) primer to both basic and more advanced aspects of Computational Complexity. Second, it is a teaching guide (teaching suggestions are sprinkled throughout the text). Third, the technical results are complemented by detailed discussions of the more philosophical implications of the covered material. I have generally enjoyed this aspect of the book. Together, though, these three aspects combine to create a potentially intimidating 600 page book that is certainly no easy reading. Indeed, I found the chosen format to be somewhat suboptimal: I would have divided the text into a technical volume and a companion, dealing with the conceptual issues and teaching suggestions.
Given these considerations, I believe the book can be used by the independent reader for self-teaching (most of the interested social scientists will probably fall in this category), but will require a significant degree of commitment and, occasionally, a reasonable degree of mathematical maturity. Alternate choices are available (e.g. Arora and Barak 2009, or the older Papadimitriou 1994). Each of these texts has strengths and weaknesses (e.g. Papadimitriou 1994 deals with the complexity of many problems from Artificial Intelligence) and the choice of a textbook is ultimately a matter of personal taste. I do believe that because of the conceptual discussions the volume under review might ultimately be the best choice for the audience of JASSS.
Finally, a word concerning the content: Not all topics and chapters in the book are equally important to the Social Scientist. An introductory course should start with Chapters 1 (Introduction and Preliminaries), 2 (Classes P, NP and NP-completeness) and 3 (Variations on P and NP). These chapters cover the topics most useful for the social scientist and their presentation is very nice). The course could then proceed with Chapter 5 (Space Complexity), Chapter 6 (Randomness and Counting) and Appendix B (presenting topics such as circuit complexity and logical proof systems). The other chapters are, in my judgment, only interesting to the more specialized reader. Others would probably better off skimming the mathematical portions and concentrating on the conceptual discussions: some of the more modern topics (such as Probabilistically Proof Systems in Chapter 9) are quite counterintuitive to the non-specialist, and will probably provide quite interesting - though not essential - lectures.
On the other hand, several topics of interest to the social scientist are not covered. This is the case, for instance, of the recent work on the complexity of finding Nash equilibria in games (for this and much more we refer the interested reader to Nisan et al. 2009). A similar case is the complexity-theoretic approach to cellular automata and related dynamical systems. People doing Social Simulations might benefit as well from an introduction the theory of rapidly mixing Markov chains (from e.g. Motwani and Raghavan 1995). It would certainly be an interesting challenge to collect these and all other relevant results and techniques in a textbook written with the Social Sciences (specifically Social Simulation) in mind.
Notes
ReferencesGOWERS, T and Barrow-Green, J and Leader, I (2009) (eds) Princeton Companion to Mathematics. Princeton: Princeton University Press
MOTWANI, R and Raghavan, P (1995) Randomized Algorithms. Cambridge: Cambridge University Press
NISAN, N, Roughgarden, T, Tardos, E, and Vazirani, V (2009) Algorithmic Game Theory. Cambridge: Cambridge University Press
PAPADIMITRIOU, C (1994) Computational Complexity. Reading, MA: Addison Wesley
Return to Contents
of this issue
© Copyright Journal of Artificial Societies and Social Simulation, 2009