Descriptive Complexity

This article is about the book. For the theory, see Descriptive complexity theory.

Descriptive Complexity is a book in mathematical logic and computational complexity theory by Neil Immerman. It concerns descriptive complexity theory, an area in which the expressibility of mathematical properties using different types of logic is shown to be equivalent to their computability in different types of resource-bounded models of computation. It was published in 1999 by Springer-Verlag in their book series Graduate Texts in Computer Science.

Topics

The book has 15 chapters, roughly grouped into five chapters on first-order logic, three on second-order logic, and seven independent chapters on advanced topics.

The first two chapters provide background material in first-order logic (including first-order arithmetic, the BIT predicate, and the notion of a first-order query) and complexity theory (including formal languages, resource-bounded complexity classes, and complete problems). Chapter three begins the connection between logic and complexity, with a proof that the first-order-recognizable languages can be recognized in logarithmic space, and the construction of complete languages for logarithmic space, nondeterministic logarithmic space, and polynomial time. The fourth chapter concerns inductive definitions, fixed-point operators, and the characterization of polynomial time in terms of first-order logic with the least fixed-point operator. The part of the book on first-order topics ends with a chapter on logical characterizations of resource bounds for parallel random-access machines and circuit complexity.

Chapter six introduces Ehrenfeucht–Fraïssé games, a key tool for proving logical inexpressibility, and chapter seven introduces second-order logic. It includes Fagin's theorem characterizing nondeterministic polynomial time in terms of existential second-order logic, the Cook–Levin theorem on the existence of NP-complete problems, and extensions of these results to the polynomial hierarchy. Chapter eight uses games to prove the inexpressibility of certain languages in second-order logic.

Chapter nine concerns the complementation of languages and the transitive closure operator, including the Immerman–Szelepcsényi theorem that nondeterministic logarithmic space is closed under complementation. Chapter ten provides complete problems and a second-order logical characterization of polynomial space. Chapter eleven concerns uniformity in circuit complexity (the distinction between the existence of circuits for solving a problem, and their algorithmic constructibility), and chapter twelve concerns the role of ordering and counting predicates in logical characterizations of complexity classes. Chapter thirteen uses the switching lemma for lower bounds, and chapter fourteen concerns applications to databases and model checking. A final chapter outlines topics still in need of research in this area.

Audience and reception

The book is primarily aimed as a reference to researchers in this area, but it could also be used as the basis of a graduate course, and comes equipped with exercises for this purpose. Although it claims to be self-contained, reviewer W. Klonowski writes that its readers need to already understand both classical complexity and the basics of mathematical logic.

Reviewer Anuj Dawar writes that some of the early promise of descriptive complexity has been dampened by its inability to bring logical tools to bear on the core problems of complexity theory, and by the need to add computation-like additions to logical languages in order to use them to characterize computation. Nevertheless, he writes, the book is useful as a way of introducing researchers to this line of research, and to a less heavily-explored way of approaching computational complexity.