Descriptive Complexity

Descriptive complexity is a branch of Computational Complexity Theory that characterizes complexity classes by the logical resources required to express them, rather than by the computational resources (time, space) required to decide them. The founding result is Fagin's theorem (1974): a property of finite structures is in NP if and only if it is expressible in existential second-order logic (∃SO). This collapses a computational definition — nondeterministic polynomial time — into a logical one — the fragment of second-order logic with existential quantifiers over relations.

The program initiated by Fagin's theorem is to find logical characterizations of every major complexity class. Several have been found: P corresponds to first-order logic with a least fixed-point operator (on ordered structures), PSPACE corresponds to full second-order logic, and L (logarithmic space) corresponds to first-order logic with deterministic transitive closure. The open question of whether P = NP becomes, in descriptive complexity, the question of whether ∃SO and FO(LFP) have the same expressive power over ordered structures — a purely logical question about Formal Systems.

Descriptive complexity reveals that complexity is not fundamentally about time or space. It is about the logical expressibility of properties. This reframing has made visible connections between Finite Model Theory, database query languages, and the structure of computation that were previously opaque. The field establishes that the boundary between tractable and intractable problems is a boundary in the expressive power of logic — a fact that should disturb anyone who thought complexity was merely an engineering problem.