Descriptive complexity is a branch of computational complexity theory and of finite model theory that characterizes complexity classes by the type of logic needed to express the languages in them. For example, PH, the union of all complexity classes in the polynomial hierarchy, is precisely the class of languages expressible by statements of second-order logic. This connection between complexity and the logic of finite structures allows results to be transferred easily from one area to the other, facilitating new proof methods and providing additional evidence that the main complexity classes are somehow "natural" and not tied to the specific abstract machines used to define them.

Specifically, each logical system produces a set of queries expressible in it. The queries – when restricted to finite structures – correspond to the computational problems of traditional complexity theory.

The first main result of descriptive complexity was Fagin's theorem, shown by Ronald Fagin in 1974. It established that NP is precisely the set of languages expressible by sentences of existential second-order logic; that is, second-order logic excluding universal quantification over relations, functions, and subsets. Many other classes were later characterized in such a manner.

When we use the logic formalism to describe a computational problem, the input is a finite structure, and the elements of that structure are the domain of discourse. Usually the input is either a string (of bits or over an alphabet) and the elements of the logical structure represent positions of the string, or the input is a graph and the elements of the logical structure represent its vertices. The length of the input will be measured by the size of the respective structure. Whatever the structure is, we can assume that there are relations that can be tested, for example "${\displaystyle E(x,y)}$ is true if and only if there is an edge from x to y" (in case of the structure being a graph), or "${\displaystyle P(n)}$ is true if and only if the nth letter of the string is 1." These relations are the predicates for the first-order logic system. We also have constants, which are special elements of the respective structure, for example if we want to check reachability in a graph, we will have to choose two constants s (start) and t (terminal).

In descriptive complexity theory we often assume that there is a total order over the elements and that we can check equality between elements. This lets us consider elements as numbers: the element x represents the number n if and only if there are ${\displaystyle (n-1)}$ elements y with ${\displaystyle y<x}$. Thanks to this we also may have the primitive predicate "bit", where ${\displaystyle bit(x,k)}$ is true if only the kth bit of the binary expansion of x is 1. (We can replace addition and multiplication by ternary relations such that ${\displaystyle plus(x,y,z)}$ is true if and only if ${\displaystyle x+y=z}$ and ${\displaystyle times(x,y,z)}$ is true if and only if ${\displaystyle x*y=z}$).

If we restrict ourselves to ordered structures with a successor relation and basic arithmetical predicates, then we get the following characterisations:

In circuit complexity, first-order logic with arbitrary predicates can be shown to be equal to AC⁰, the first class in the AC hierarchy. Indeed, there is a natural translation from FO's symbols to nodes of circuits, with ${\displaystyle \forall ,\exists }$ being ${\displaystyle \land }$ and ${\displaystyle \lor }$ of size n. First-order logic in a signature with arithmetical predicates characterises the restriction of the AC⁰ family of circuits to those constructible in alternating logarithmic time. First-order logic in a signature with only the order relation corresponds to the set of star-free languages.

First-order logic gains substantially in expressive power when it is augmented with an operator that computes the transitive closure of a binary relation. The resulting transitive closure logic is known to characterise non-deterministic logarithmic space (NL) on ordered structures. This was used by Immerman to show that NL is closed under complement (i. e. that NL = co-NL).