COOKIES: By using this website you agree that we can place Google Analytics Cookies on your device for performance monitoring. |

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

## Logics with algebraic operatorsAdd 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)
- Computer Laboratory talks
- 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. |
## Other listsCLIO - CU history Society Body in Mind Faculty of Economics## Other talksFukushima and the Law ADMM for Exploiting Structure in MPC Problems Why Do We Need Another Biography of Hitler? BOOK LAUNCH: Studying Arctic Fields: Cultures, Practices, and Environmental Sciences An investigation into hepatocyte expression and prognostic significance of senescence marker p21 in canine chronic hepatitis Land of Eagles - Albania: from closed nation to wildlife paradise - where next? |