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.
|