Notes / Teaching Materials

Lecture Notes

1. 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 = ESO-Horn(<)); 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., order-invariance, 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.