University of Cambridge > > Semantics Lunch (Computer Laboratory) > Logics with algebraic operators

Logics with algebraic operators

Add to your list(s) Download to your calendar using vCal

If you have a question about this talk, please contact Sam Staton.

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!

This talk is part of the Semantics Lunch (Computer Laboratory) series.

Tell a friend about this talk:

This talk is included in these lists:

Note that ex-directory lists are not shown.


© 2006-2023, University of Cambridge. Contact Us | Help and Documentation | Privacy and Publicity