Details of Grant 

EPSRC Reference:	GR/K96564/01
Title:	COMPLEXITY THEORY FROM LOGIC.
Principal Investigator:	Stewart, Professor IA
Other Investigators:
Researcher Co-Investigators:
Project Partners:
Department:	Mathematics
Organisation:	University of Leicester
Scheme:	Standard Research (Pre-FEC)
Starts:	30 October 1996	Ends:	29 October 1999	Value (£):	98,758
EPSRC Research Topic Classifications:	Fundamentals of Computing
EPSRC Industrial Sector Classifications:
Related Grants:
Panel History:
Summary on Grant Application Form
The proposed project will develop and extend strong links between computer science, mathematics and logic. We intend to investigate the relationships between different logical classification mechanisms for problems, particularly for problems complete for some complexity class (particularly 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 Lindstrom 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. We also intend to exhibit logical hierarchies in complexity classes by developing and playing extended Ehrenfeucht-Fraisse games.
Key Findings
This information can now be found on Gateway to Research (GtR) http://gtr.rcuk.ac.uk
Potential use in non-academic contexts
This information can now be found on Gateway to Research (GtR) http://gtr.rcuk.ac.uk
Impacts
Description This information can now be found on Gateway to Research (GtR) http://gtr.rcuk.ac.uk Summary Date Materialised
Sectors submitted by the Researcher
This information can now be found on Gateway to Research (GtR) http://gtr.rcuk.ac.uk
Project URL:
Further Information:
Organisation Website:	http://www.le.ac.uk