Duration: 1:23:35

671 views

19

In Descriptive Complexity, we ask how rich a logical language is needed to describe a given computational problem. It is natural that there might sometimes be a relation between descriptive complexity and traditional computational complexity. Remarkably, there is an isomorphism. In fact, the most important complexity classes have very natural descriptive characterizations. I will give a survey about descriptive complexity including recent progress in understanding dynamic problems – where we are computing properties of inputs that change over time. There are applications to database problems as well as to reasoning about the correctness of programs.