**
Natasha Alechina School of Computer Science and ITUniversity 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:

- Lecture 1: Introduction and exercises. Structures, first order logic (FO), first order queries.
- Lecture 2: Compexity classes. Turing machines, encoding of structures, class hierarchies, completeness under reductions.
- Lecture 3: First order reductions. FO queries can be evaluated in
deterministic logspace; REACH
_{a}is P-complete under first-order reductions. - Lecture 4: Immerman - Vardi theorem. FO(LFP), polynomial bound on the number
of iterations, expressing REACH
_{a}as an FO(LFP) formula.

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.