Descriptive complexity measure a problem in terms of the difficulty to express it. At first look this seems to have nothing to do with computational measures such as time and space. However it does have intimate links with classical computational complexity.

The most celebrated one is Fagin’s theorem linking the complexity class NP with the expressive power of existential second-order logic.

In this lecture we will study the Abiteboul-Vianu theorem saying that the separation of PTime and PSpace can be rephrased in terms of expressive powers of partial fixpoints versus least fixpoints.