Playing games with transitive closure
Dr Richard Gault, Department of Maths and Computer Science, University of Leicester

Abstract: The question of whether or not NP = co-NP is one of the most fundamental open problems in theoretical computer science. In a seminal result in the early 1970s, Fagin characterised NP as the class of problems expressible using existential second-order logic, and went on to show that an important subclass of this -- monadic NP -- is, in fact, not closed under complementation.

I shall review this early work and show how it may be extended, with particular reference to the additional power which a transitive closure operator provides. I shall show that this resulting logic also has an important subclass which is not closed under complementation.

This seminar was held at the Department of Computer Science, Royal Holloway, University of London on 2 July 1998.

back