BEGIN:VCALENDAR
VERSION:2.0
PRODID:-//Talks.cam//talks.cam.ac.uk//
X-WR-CALNAME:Talks.cam
BEGIN:VEVENT
SUMMARY:Logics with algebraic operators - Bjarki Holm (University of Cambr
 idge)
DTSTART:20101213T124500Z
DTEND:20101213T140000Z
UID:TALK27337@talks.cam.ac.uk
CONTACT:Sam Staton
DESCRIPTION:One of the main open questions in finite model theory is wheth
 er there is a \nlogic that can express exactly all the polynomial-time com
 putable \nproperties of finite structures. By a theorem of Fagin we know t
 hat the \nclass NP is captured by the existential fragment of second-order
  logic. \nFinding a logic for polynomial time would therefore allow logica
 l (in \nparticular\, model-theoretic) techniques to be applied to one of t
 he most \nimportant questions of computational complexity\, that whether P
  = NP.\n\nOver the past three decades\, there have been a number of attemp
 ts to define \na logic for polynomial time\, mainly by considering extensi
 ons of \nfirst-order and fixed-point logics. Recently it has been shown th
 at all the \nknown shortcomings of these previously proposed logics relate
  to their \ninability to define certain basic properties in linear algebra
 \, such as the \nsolvability of equations over an Abelian group or the ran
 k of a matrix over \na finite field. This has focused attention on the exp
 ressive power of \nlogics equipped with elementary algebraic operators. In
  this talk I will \nsurvey recent results in this area and discuss some on
 going work.\n\nThe talk will be kept "semantics friendly" and should be an
  excellent \nwarm-up for the evening's Theory Christmas dinner!\n
LOCATION:Room FW26\, Computer Laboratory\, William Gates Building
END:VEVENT
END:VCALENDAR