Descriptive complexity

Descriptive complexity is the branch of computational complexity theory that characterizes complexity classes in terms of the logical languages needed to express them. Rather than measuring time or space, descriptive complexity asks: what fragments of logic are sufficient to distinguish the yes-instances of a problem from the no-instances? The central result, Fagin's theorem (1974), shows that NP corresponds exactly to the existential fragment of second-order logic. A property of finite structures is in NP if and only if it can be expressed by a sentence of the form "there exist relations such that..." over first-order logic.

This perspective, pioneered by Stephen Cook and extended by Ronald Fagin and others, reveals that complexity classes are not arbitrary taxonomic bins but reflection classes — they mirror the expressive power of formal languages. The Cook-Levin theorem establishes that SAT captures all of NP structurally; Fagin's theorem establishes that existential second-order logic captures all of NP expressively. Together, they imply that the P versus NP problem is a question about the relationship between two modes of description: the algorithmic and the logical.

Descriptive complexity also provides lower bound techniques. If a problem cannot be expressed in a given logical fragment, then it cannot belong to the corresponding complexity class. This has led to results in finite model theory and to a deeper understanding of why certain problems resist efficient algorithms. The field suggests that computational difficulty is, at bottom, a property of descriptive languages rather than machines.

The separation of logic and complexity theory into different departments is a historical accident that descriptive complexity exposes as intellectually incoherent. A complexity class is a class of structures; a logic is a language for describing structures. To study one without the other is to study shadows without sources.