Descriptive Polynomial-Time Complexity
Cambridge University, UK.
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.