What question did this study set out to answer?

The aim is to explore how finite model theory relates to complexity theory, particularly through descriptive complexity.

February 16, 2026Open Access

Model Theory and Complexity Theory

Key Points

The aim is to explore how finite model theory relates to complexity theory, particularly through descriptive complexity.
Analyzed classical results like Fagin's theorem and Immerman’s characterization of P.
Utilized Ehrenfeucht–Fraïssé games and pebble games to study expressibility.
Applied the framework to the divisibility problem DIV_k and finite group types, including dihedral groups.
Established upper and lower bounds on quantifier depth and variable count for distinguishing groups.
Demonstrated significant insights into the structure of finite abelian groups and dihedral groups.
Identified open problems and introduced abstract elementary classes for further model-theoretic study.

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

Ask AI

Helpful

Bookmark

View Full Paper