Abstract

One of the main open questions in finite model theory is whether there is a logic that can express exactly all the polynomial-time computable properties of finite structures. By a theorem of Fagin we know that the class NP is captured by the existential fragment of second-order logic. Finding a logic for polynomial time would therefore allow logical (in particular, model-theoretic) techniques to be applied to one of the most important questions of computational complexity, that whether P = NP.

Over the past three decades, there have been a number of attempts to define a logic for polynomial time, mainly by considering extensions of first-order and fixed-point logics. Recently it has been shown that all the known shortcomings of these previously proposed logics relate to their inability to define certain basic properties in linear algebra, such as the solvability of equations over an Abelian group or the rank of a matrix over a finite field. This has focused attention on the expressive power of logics equipped with elementary algebraic operators. In this talk I will survey recent results in this area and discuss some ongoing work.

The talk will be kept “semantics friendly” and should be an excellent warm-up for the evening’s Theory Christmas dinner!