Logics with algebraic operators

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

• Bjarki Holm (University of Cambridge)
• Monday 13 December 2010, 12:45-14:00
• Room FW26, Computer Laboratory, William Gates Building.

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.

This talk is included in these lists:

• All Talks (aka the CURE list)
• Cambridge talks
• Department of Computer Science and Technology talks and seminars
• Interested Talks
• Room FW26, Computer Laboratory, William Gates Building
• School of Technology
• Semantics Lunch (Computer Laboratory)
• Trust & Technology Initiative - interesting events
• bld31
• yk373's list

Note that ex-directory lists are not shown.