Descriptive Complexity

Natasha Alechina
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:

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.

Recommended textbook: Neil Immerman, Descriptive Complexity , Springer 1999. I hope to cover the first four chapters - it may help if you look at the first two chapters before the course starts!

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.