Descriptive Complexity of small Complexity Classes

Descriptive complexity theory relates the computational complexity of
algorithmic problems with the descriptional complexity of the problems. It can
be shown that, boldly stated, problems that are hard to solve on a computer
are hard to describe in a formal language and vice versa. More precisely,
descriptive complexity theory has established logical characterisations for
many natural complexity classes. Such characterisations give an approach to
computational complexity that is independent of specific machine models and
representations of the input. Logical characterisations of complexity classes
are also of interest in database theory. As a matter of fact, the main open
question of descriptive complexity, the question of whether there is a logic
that capture polynomial time, was first posed in a fundamental paper on
database query languages by Chandra and Harel (1982).

While logical characterisations are known for the complexity class NP and most
natural complexity classes extending NP, no such characterisations are known
for subclasses of NP and, in particular, for the class PTIME. The question of
a logical characterisation of PTIME is one of the main open problems in finite
model theory and database theory.

In this project, we will study various aspect of the descripte complexity
theory of the class PTIME and its subclasses.