Complexity Theory from Logic
Source of Funding: Engineering and Physical Sciences
Research Council (EPSRC)
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.