Model Theory and Complexity Theory

This presentation explores the intersection of finite model theory and complexity theory, with a focus on descriptive complexity—a framework that classifies computational problems based on the logical languages needed to express them. It highlights classical results such as Fagin’s theorem (NP = Σ₁¹) and Immerman’s characterization of P, and introduces tools like Ehrenfeucht–Fraïssé games and pebble games to study expressibility within fragments of second-order logic. The presentation then applies this framework to analyze the divisibility problem DIVₖ and the descriptive complexity of finite abelian groups and dihedral groups, establishing upper and lower bounds on quantifier depth and variable count for sentences that distinguish non-isomorphic groups. It concludes with open problems and an introduction to abstract elementary classes as a broader semantic framework for studying model-theoretic properties beyond first-order logic.