Descriptive Complexity

Origin. Fagin (1974), Immerman, Vardi (1982). Characterizes computational complexity classes by logical expressiveness over finite structures. Companion to Finite Model Theory, focused on the capture program.

Models. A complexity class is "captured" by a logic when exactly the class-decidable properties of finite structures are the logic-definable ones. Resources correspond to expressive power, independent of any machine model.

Formalism.

Capture: Logic L captures class C iff for every property P of finite (ordered) structures: P ∈ C ⟺ P definable in L.

Fagin's theorem: NP = ∃SO (existential second-order). No ordering required.

Immerman-Vardi: P = FO(LFP) = FO(IFP) on ordered structures. Least/inflationary fixed point.

Transitive closure: NL = FO(TC). L = FO(DTC) (deterministic TC). Immerman-Szelepcsényi: NL closed under complement.

Capture catalog (ordered): AC⁰ = FO(BIT). L = FO(DTC). NL = FO(TC). P = FO(LFP). PSPACE = FO(PFP) = SO(TC). EXPTIME = SO(LFP).

Methodology: Reductions rendered as first-order interpretations. Lower bounds via Ehrenfeucht-Fraïssé games and quantifier rank.

Symbols.

Symbol	Unicode	Name	Meaning
∃SO	—	Existential SO	Fagin's logic for NP
FO(LFP)	—	Least fixed point	Logic for P
FO(TC)	—	Transitive closure	Logic for NL
FO(PFP)	—	Partial fixed point	Logic for PSPACE

Metatheory. Machine-independent complexity. Fagin's characterization of NP needs no order; the fixed-point captures of P and PSPACE do. Whether a logic captures P on unordered structures is the central open problem. Ties directly to database query complexity.

Applies to. Complexity theory foundations. Database query languages. Constraint satisfaction. Parameterized complexity. Separation questions via logical inexpressibility.

Limitations. Most captures require a linear order on the universe. Capturing P in general remains open. Practical only for structural, not numeric, computation.

See Finite Model Theory for the broader theory of logic over finite structures (0-1 laws, locality).