Complexity: Structures and Specifications

A central achievement of Complexity Theory was the development of the
theory of NP-completeness, 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 3-colourable) 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
first-order logic on graphs.

The talk will assume little background knowledge of either logic
or graph theory.