Descriptive Complexity Theory

This presentation explores the intersection of mathematical logic and computational complexity by classifying computational problems based on their expressibility in logical formalisms. It introduces first-order logic and its extensions, such as second-order logic, and discusses key results like Fagin’s theorem (NP = Σ₁¹) and Immerman’s characterization of P using least fixed-point logic. The presentation also examines expressibility hierarchies within Σ₁¹, applies descriptive complexity to distinguish finite abelian groups, and introduces Abstract Elementary Classes as a generalization of first-order model theory. Open problems are highlighted throughout, focusing on refining expressibility hierarchies and extending results to broader classes of structures.