3.30 p.m.
Descriptive Polynomial-Time Complexity
Anuj Dawar
Cambridge University, UK.
22-12-09

---

Abstract

The long-standing open problem in the area of descriptive complexity is that of finding a logical characterisation of polynomial time. In this talk, I will give an exposition of the problem, and past approaches to it. In particular, we will talk about fixed-point logics, extensions of these with counting and an explanation of the Cai-Fuerer-Immerman result that shows these are not sufficient to express all of polynomial time.