Descriptive Complexity

Complexity classes are normally defined semantically, by a resource bound on a machine: polynomial time, logarithmic space, polynomial-size circuits. Descriptive complexity works the other way around. You start with a logical language, a set of syntactic rules for writing sentences, and the complexity class is whatever that language can express. Neil Immerman's map of the field lines the two up floor by floor, from FO equals $A{C}^0$ at the bottom, through L, NL, and P, up to NP, the polynomial hierarchy, PSPACE, and EXPTIME. We don't know that all of these classes are really different, since even P versus NP is open, but this is the map of what might be different.

What logic talks about#

A vocabulary is a list of relation symbols, each with an arity; for graphs it has one binary symbol $E$, and that's it. A structure over a vocabulary is a finite set of elements, the universe, plus an actual relation for each symbol. A graph: the universe is the vertices, and $E(u,v)$ holds when there is an edge from $u$ to $v$. A string: the universe is the positions, unary predicates mark which symbol sits where, and a binary relation orders the positions.

The structures in this story come with a built-in linear order on the universe, letting the logic refer to "the first element" or "the element at position $k$"; without it, elements would be interchangeable. Keep that flag in mind; it returns at the end.

First-order logic and its horizon#

In first-order logic, variables range over elements of the universe; you can test relations, combine with and, or, not, and quantify. Is there a vertex adjacent to all others? $\exists x\forall yE(x,y)$. Is the graph triangle-free? A sentence with three universal quantifiers says no edge triple closes a triangle. On ordered structures with built-in arithmetic, first-order logic captures uniform $A{C}^0$.

But here is what first-order logic cannot say: is the graph connected? A path might pass through one intermediate vertex, or ten, or $n$, while over the bare graph vocabulary a first-order sentence has a fixed number of quantifiers and only sees a bounded neighborhood of each vertex. The built-in order breaks that local intuition but not the result, which follows from FO sitting inside $A{C}^0$ and parity reducing to connectivity. Connectivity needs unbounded reach, and this is where the hierarchy begins.

Operators for reachability#

Add one operator: transitive closure. $\left[T{C}_{x,y}\phi \right(x,y\left)\right](s,t)$ asks whether, starting from $s$, you can reach $t$ by repeatedly following the relation $\phi$ defines. Immerman proved that FO[TC] captures NL, nondeterministic logspace, on ordered structures, and the correspondence is immediate: the canonical NL-complete problem is exactly graph reachability. The deterministic variant, requiring exactly one successor at each step, gives FO[DTC] equals L.

Fixed points capture P#

Transitive closure is the least fixed point of "extend paths by one edge," and the least fixed point operator generalizes it. Start with an empty relation $R$. A formula $\phi$ says which tuples belong in $R$, based on what is already there and on the input; apply it repeatedly until nothing changes. The formula must be positive in $R$, never using $R$ under a negation: that syntactic condition makes the operator monotone, so the relation only grows, and on a finite structure it stabilizes.

The Immerman-Vardi theorem: FO[LFP] captures P on ordered structures, proved independently by Immerman and Vardi in 1982. One direction is easy: a $k$-ary relation holds at most $n^k$ tuples and each iteration adds at least one, so the fixed point arrives within $n^k$ rounds of polynomial-time formula evaluation. For the other, encode each configuration of a polynomial-time Turing machine as a tuple, with the ordering addressing tape cells; the operator adds whichever configurations follow from ones already reached, and you check the fixed point for an accepting one.

Polynomial time, a resource bound on a machine, is exactly first-order logic plus one operation: iterate a rule to its fixed point.

Fagin's theorem#

Second-order logic is a different kind of jump: variables now range over relations of any arity, subsets of vertices, colorings, arbitrary $k$-ary relations. Fagin's theorem, from 1974: existential second-order logic captures NP. A property is in NP exactly when it has the form "there exist relations such that a first-order sentence holds."

NP is defined by certificates: a polynomial-size certificate that a polynomial-time verifier accepts. The certificate becomes the existentially quantified relation. But the verifier runs in polynomial time, which is FO[LFP], so why does plain FO suffice in the body? Because verification decomposes into local checks. A verifier checking a proposed 3-coloring asks whether each vertex has exactly one color and whether adjacent vertices differ: every check touches a bounded number of elements, and only the number of checks is large. In general, compile the verifier into a Boolean circuit and existentially quantify over the value of every gate, the entire computation trace. All that remains is checking each gate against its inputs, a constraint on three bits: a universal first-order sweep over local checks. The existential quantifiers do the heavy lifting; first-order logic does the bookkeeping.

Three-colorability in this form: there exist three unary predicates, red, green, blue, such that every vertex gets exactly one color and no edge joins two vertices of the same color. Every constraint mentions at most two vertices.

Pause and try: write an existential second-order sentence for "the graph has a Hamiltonian path."

Guess a binary relation $<$ and assert that it is a strict linear order and that consecutive vertices are adjacent, where "$y$ succeeds $x$" means $x<y$ with no $z$ strictly between. Each condition is first-order; the existential quantifier guesses the order in which the path visits the vertices, and everything else is local checking.

The hierarchy is quantifier alternation#

What sits above NP? Suppose you must find an assignment to $x$ that makes a formula true for all assignments to $y$: one round of guessing isn't enough. That is ${\mathrm{\Sigma }}_{2^p}$, and the polynomial hierarchy generalizes it, one alternation of exists and for-all per level, with PH the union of all levels. With Turing machines this takes oracle machinery. In the descriptive world: $\exists R$ [FO] is NP, $\forall R$ [FO] is coNP, $\exists R\forall S$ [FO] is ${\mathrm{\Sigma }}_{2^p}$, and so on. Full second-order logic captures PH.

And the bottom of every level is plain FO, not FO[LFP]: the hardness of these classes is not in the base computation but in the alternation of quantifiers over relations.

The pattern continues upward. Partial fixed points, which drop the monotonicity requirement and so may oscillate before stabilizing, capture PSPACE; second-order logic with least fixed points captures EXPTIME. Every floor has two names, a logic on the left and a complexity class on the right. Like the real numbers, definable by Dedekind cuts or by Cauchy sequences, these classes have multiple independent characterizations: they are not artifacts of the Turing machine. The Church-Turing thesis says what is computable doesn't depend on the model; descriptive complexity extends the insight to what is efficiently computable.

The logical lens also refines reductions. Studying P with polynomial-time reductions is circular, a ruler measuring itself, but FO reductions ($A{C}^0$) and FO projections, where each piece of the output depends on at most one element of the input, are weaker than the classes they probe. The textbook reduction from 3-colorability to SAT is already a projection, and SAT is NP-complete under even these weakest reductions: its structure aligns so tightly with NP that the encoding is almost a relabeling.

What is P without order?#

Everything above holds on ordered structures. The order lets logic address elements by position and encode a Turing machine tape. Without order, elements are anonymous, distinguishable only by their relations. Fagin's theorem survives, since an existential quantifier can guess an ordering, but FO[LFP] on unordered structures is weaker than P.

The central open problem, posed by Chandra and Harel in 1982: is there a logic that captures P on all finite structures? The natural candidate was fixed-point logic with counting, FP+C. In 1992, Cai, Fürer, and Immerman ruled it out with pairs of genuinely non-isomorphic graphs that FP+C cannot distinguish but a polynomial-time algorithm can: replace every edge of a base graph with a twisted or untwisted gadget, and the global parity of the twists separates the pair. FP+C can count gadgets in each state but cannot coordinate parity across the whole graph; an algorithm with an ordering walks through and accumulates it.

The standing proposal, from Blass, Gurevich, and Shelah, is Choiceless Polynomial Time with counting: computation over hereditarily finite sets built from the input's elements, with one constraint, that you may never choose a distinguished element from an unordered collection, the symmetry-breaking a Turing machine's tape performs implicitly. Whether CPT with counting equals P on unordered structures is unknown. If it does, polynomial time never truly needs to break symmetry; if it doesn't, some polynomial-time properties cannot be computed without arbitrary choices.

If you remember three things#

1. Descriptive complexity defines classes by syntax: FO[LFP] equals P (Immerman-Vardi) and existential second-order logic equals NP (Fagin) on ordered structures.
2. At every level of the polynomial hierarchy the base is plain first-order logic; the power lives entirely in the quantifier structure.
3. Whether any logic captures P without a built-in order is open: Cai-Fürer-Immerman eliminated counting, and Choiceless Polynomial Time with counting is the live candidate.