Computer Laboratory
University of Cambridge
4pm Tuesday 25th of November, 2008
Room 4.31/4.33, Informatics Forum
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.