descriptive complexity
Complexity classes are usually defined by counting resources: how much time, how much memory a machine uses. Descriptive complexity offers a startlingly different lens, one that never mentions a machine at all. Its question is: how rich a logical language do you need just to express a problem? It turns out that the difficulty of computing a problem and the expressive power of the logic needed to describe it are two faces of the same coin.
The idea is to treat an input (a graph, a string, a structure) as a mathematical object that a logical formula can talk about, and ask what logical operators you must allow to state a given property. Plain first-order logic (quantifiers over individual elements: 'there exists a vertex such that...') captures only fairly simple, local properties. Adding the ability to quantify over relations or sets — second-order logic — or adding a least-fixed-point operator that expresses recursion, jumps you up to whole complexity classes. The remarkable empirical fact is that natural complexity classes correspond exactly to natural logics: P, NP, PSPACE and others each have a clean logical characterization, and crucially these correspondences are machine-independent — they do not mention time, tape, or steps at all.
Why does this matter? It reframes the great open questions as questions about the power of logic. For example, since NP equals existential second-order logic (Fagin's theorem, its own entry), the question of whether P equals NP becomes a question about whether a certain weaker logic can express everything a stronger one can. This gives logicians a foothold on complexity, and it powers practical tools: a query in a database language like SQL is essentially a first-order (or fixed-point) formula, so descriptive complexity tells us precisely how hard such queries can be. The theory builds a bridge between 'what can be computed efficiently' and 'what can be said'.
Graph 2-colourability (is a graph bipartite?) is expressible by saying 'there exists a set S of vertices such that every edge has exactly one endpoint in S' — an existential second-order statement, and indeed the problem is in NP (in fact in P). The need to quantify over a SET of vertices, not just individual ones, is exactly what lifts this beyond plain first-order logic.
Descriptive complexity matches complexity classes to logics — power to compute equals power to express.
These logical characterizations are machine-independent — they define complexity classes without ever mentioning time, memory, or a Turing machine. That is precisely what makes them powerful and surprising, not a defect.