Computational complexity was originally defined in terms of the natural entities of time and space, and the term complexity was used to denote the time or space used in the computation. Rather than checking whether an input satisfies a property S, a more natural question might be: what is the complexity of expressing the property S? These two issues --- checking and expressing --- are closely related. It is startling how closely tied they are when the latter refers to expressing the property in first-order logic of finite and ordered structures.

Begun in 1974 by Fagin, descriptive complexity has characterized all major notions of complexity in terms of the richness of logical languages needed to describe problems. Descriptive complexity is part of finite model theory, and it ties together logic and computer science. It has major applications to the theory of databases and computer-aided verification.

This self-contained textbook introduces the methods and results of descriptive complexity together with its applications. With many examples and exercises, it may be used for a graduate or advanced undergraduate course.

• Cover
• Table of Contents
• Bibliography
• Corrections, annotations, additions
• Ordering: currently available at: Springer.
• Sample Chapters: 0 - 2, 3, 5, 6, 7, 13