University of Leicester

informatics

Complexity Theory from Logic

Source of Funding: Engineering and Physical Sciences Research Council (EPSRC)
Amount: £91,394
Duration: April 1996 - March 1999
Principal Investigator: Prof. Iain Stewart
Other Investigator: Dr. Juha Nurmonen

We intend to develop and extend strong links between computer science, mathematics and logic by investigating the relationships between different logical classification mechanisms for problems, particularly for problems complete for some complexity class (such as NP) via some resource-bounded reduction. Some of the mechanisms we have in mind are: completeness for some complexity class via logical translations, with and without built-in relations; expressibility of extensions of first-order logic using uniform sequences of generalized quantifiers corresponding to the problem; and definability in bounded-variable infinitary logic. Our general aim is to understand better the notion of completeness in complexity theory.

© University of Leicester 15th December 2000. Last modified: 8th January 2004, 14:32:32.
Informatics Web Maintainer. This document has been approved by the Head of Department.