Descriptive Complexity (Texts in Computer Science) (Hardcover)

The intended audience already has some knowledge of logic and computational complexity. While the first two chapters do cover the necessary background, the reader unfamiliar with the topics will probably find the treatment there far too condensed and prefer to look at, say, Enderton's ``A Mathematical Introduction to Logic'' and Papadimitriou's ``Computational Complexity'' before starting on this book.

The first two chapters are only intended as summaries; the remainder of the book is well-paced. Immerman starts to show correspondences between descriptive and computational complexity and introduces fixed-point logics and parallel machines, moving on to game-theoretic techniqes for showing that some properties can't be expressed in first-order logic. Next, comes second-order logic and Fagin's theorem, which states that the well-known complexity class NP is equivalent to existential second-order logic. This, coupled with the equivalence of P and fixed-point logic on ordered structures provides a purely logical viewpoint on the famous P=NP? question.

Immerman generally assumes a fairly rich first-order language. Structures are usually equipped with a linear order on their elements and often with arithmetic operators on this ordered domain and constants denoting the least and greatest elements. Unfortunately, keeping track of which of these assumptions are in place at any point in the text can be confusing, especially when referring back to the book later. Chapter 12 investigates the case where none of these assumptions are made and surveys attempts to capture the class P on unordered structures, particularly the addition of counting quantifiers to fixed-point logic.

Other topics covered include the closure under complementation of nondeterministic space classes (for which the author and Robert Szelepcsényi received the 1995 Gödel Prize), transitive closure logics and the class PSPACE.

The book contains a reasonable number of exercises scattered through the text. Some are interesting and illuminating but rather too many just ask for proofs of theorems where the proof hasn't been included in the text. This is usually because the proof is routine and wouldn't contribute much to the text and, therefore, makes a boring exercise.

Annoyingly, ``Desctiptive Complexity'' has not been well proof-read and contains too many typos, some of which are listed on the author's home page. Nonetheless, the author's enthusiasm for the subject is clear and the book remains very readable. For readers interested in taking the subject further, each chapter ends with a section of ``historical notes and suggestions for further reading''. References are also given for most results in the text.