Chennai Mathematical Institute

Seminars




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.





Google
Search WWW Search cmi.ac.in