Complexity: Structures and Specifications
Anuj Dawar ( Cambridge )

16:30 2nd December 2008 ( week 8, Michaelmas Term 2008 )Lecture Theatre B
A central achievement of Complexity Theory was the development of the
theory of NPcompleteness, which gave an explanation for the apparent
intractability of a large number of problems. A problem in this sense
is typically given by a class of instances (for example, graphs) and a
specified property (such as that a graphs is 3colourable) that must be
decided. We now know that tractability can be recovered in some cases
by restricting the class of instances to structurally simple ones, or
by restricting the properties we can specify. To formalise the former
kinds of restrictions, we generally look to structural graph theory
while to formalise the latter one naturally turns to formal logic.
In this talk we review a number of results on the complexity of
evaluating logical specifications in restricted classes of graphs,
which can be cast in this light  particularly on the evaluation of
firstorder logic on graphs.
The talk will assume little background knowledge of either logic
or graph theory.