Descriptive Complexity: Survey and Recent Progress

Опубликовано 27 июня 2016, 22:26

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.