Home
Notes / Teaching Materials
Lecture Notes

A Quick and Unorthodox Introduction to Descriptive Complexity
Section 1 contains an informal introduction to model theory and formal
logic. Sections 2 and 3 then provide a coverage of Fagin's theorem (NP
= ESO) and Grädel's theorem (P = ESOHorn(<)); the "easy
direction" of each of these proofs is given in detail; a proof sketch
is given of the other. Logics for NL and L in terms of SO fragments
are also briefly discussed. Section 4 contains details on invariance
(e.g., orderinvariance, etc.), numerous references to results
surrounding FO, FO(<), and FO(+,×), and other miscellaneous
topics. Exercises are included throughout and solutions are provided
at the end.