Model Theory and Complexity Theory

Abstract

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_k 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.