''Descriptive Complexity'' is a book in mathematical logic and

computational complexity theory In theoretical computer science and mathematics, computational complexity theory focuses on classifying computational problems according to their resource usage, and relating these classes to each other. A computational problem is a task solved ...

Neil Immerman Neil Immerman (born 24 November 1953, Manhasset, New York) is an American theoretical computer scientist, a professor of computer science at the University of Massachusetts Amherst.

. 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 First-order logic—also known as predicate logic, quantificational logic, and first-order predicate calculus—is a collection of formal systems used in mathematics, philosophy, linguistics, and computer science. First-order logic uses quantifi ...

, 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 In mathematics and computer science, the BIT predicate or Ackermann coding, sometimes written BIT(''i'', ''j''), is a predicate that tests whether the ''j''th bit of the number ''i'' is 1, when ''i'' is written in binary. History The BIT pre ...

, and the notion of a first-order query) and complexity theory (including formal languages, resource-bounded

complexity class In computational complexity theory, a complexity class is a set of computational problems of related resource-based complexity. The two most commonly analyzed resources are time and memory. In general, a complexity class is defined in terms of ...

es, and

complete problem In computational complexity theory, a computational problem is complete for a complexity class if it is, in a technical sense, among the "hardest" (or "most expressive") problems in the complexity class. More formally, a problem ''p'' is called h ...

s). 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 machine In computer science, a parallel random-access machine (parallel RAM or PRAM) is a shared-memory abstract machine. As its name indicates, the PRAM is intended as the parallel-computing analogy to the random-access machine (RAM) (not to be confused ...

s and

circuit complexity In theoretical computer science, circuit complexity is a branch of computational complexity theory in which Boolean functions are classified according to the size or depth of the Boolean circuits that compute them. A related notion is the circu ...

. 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 Fagin's theorem is the oldest result of descriptive complexity theory, a branch of computational complexity theory that characterizes complexity classes in terms of logic-based descriptions of their problems rather than by the behavior of algorithm ...

characterizing

nondeterministic polynomial time In computational complexity theory, NP (nondeterministic polynomial time) is a complexity class used to classify decision problems. NP is the set of decision problems for which the problem instances, where the answer is "yes", have proofs v ...

in terms of existential second-order logic, the

Cook–Levin theorem In computational complexity theory, the Cook–Levin theorem, also known as Cook's theorem, states that the Boolean satisfiability problem is NP-complete. That is, it is in NP, and any problem in NP can be reduced in polynomial time by a determ ...

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 In mathematics, the transitive closure of a binary relation on a set is the smallest relation on that contains and is transitive. For finite sets, "smallest" can be taken in its usual sense, of having the fewest related pairs; for infinit ...

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 In computational complexity theory, PSPACE is the set of all decision problems that can be solved by a Turing machine using a polynomial amount of space. Formal definition If we denote by SPACE(''t''(''n'')), the set of all problems that can b ...

. 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 In computational complexity theory, Håstad's switching lemma is a key tool for proving lower bounds on the size of constant-depth Boolean circuits. Using the switching lemma, showed that Boolean circuits of depth ''k'' in which only AND, OR, and ...

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.

References

{{reflist, refs= {{citation , last = Dawar , first = Anuj , journal = Mathematical Reviews , mr = 1732784 , title = Review of ''Descriptive Complexity'' , year = 2001 {{citation , last = Klonowski , first = W. , doi = 10.1155/S1026022601000061 , journal = Discrete Dynamics in Nature and Society , pages = 57–62 , title = Review of ''Descriptive Complexity'' , volume = 6 , year = 2001, doi-access = free {{citation , last = Lindell , first = Steven , date = December 2001 , doi = 10.2307/2687799 , issue = 4 , journal =

The Bulletin of Symbolic Logic The Association for Symbolic Logic (ASL) is an international organization of specialists in mathematical logic and philosophical logic. The ASL was founded in 1936, and its first president was Alonzo Church. The current president of the ASL is ...

, jstor = 2687799 , pages = 525–527 , title = Review of ''Descriptive Complexity'' , volume = 7 {{citation , last = Schöning , first = Uwe , author-link = Uwe Schöning , journal =

zbMATH zbMATH Open, formerly Zentralblatt MATH, is a major reviewing service providing reviews and abstracts for articles in pure and applied mathematics, produced by the Berlin office of FIZ Karlsruhe – Leibniz Institute for Information Infrastructu ...

, title = Review of ''Descriptive Complexity'' , zbl = 0918.68031 Descriptive complexity Mathematics books 1999 non-fiction books