School of Computer Science and IT
University of Nottingham
Descriptive complexity studies the relation between formal languages and computational resources (space and time) required to solve problems formulated in those languages. It turns out that many complexity classes, such as P and NP, have an independent logical characterisation (first order logic with inductive definitions and existential second order logic, respectively). Techniques and results of descriptive complexity theory are used in database theory and computer aided verification.
The aim of the course is to introduce the basics of descriptive complexity theory and prove the theorem (due to Immerman and Vardi) that, on ordered structures, polynomial time queries are exactly those which can be formulated in first order logic plus the least fixed point operator.
Below is the preliminary schedule of lectures:
This course will be taught at the University of Nottingham during October and November and March 2000, as part of Midlands Graduate School in the Foundations of Computer Science.