EPSRC logo

Details of Grant 

EPSRC Reference: GR/S06721/01
Title: The Role of Choice in Descriptive Complexity
Principal Investigator: Dawar, Professor A
Other Investigators:
Researcher Co-Investigators:
Project Partners:
Department: Computer Science and Technology
Organisation: University of Cambridge
Scheme: Standard Research (Pre-FEC)
Starts: 01 April 2003 Ends: 31 March 2006 Value (£): 148,357
EPSRC Research Topic Classifications:
Fundamentals of Computing
EPSRC Industrial Sector Classifications:
Related Grants:
Panel History:  
Summary on Grant Application Form
Whether or not there is a logical language that expresses exactly the feasibly computable properties of finite relational structures is a long-standing open problem in descriptive complexity theory. It is closely tied to the search for query languages for relational databases that are highly expressive but all of whose queries can be computed efficiently. The most expressive such languages proposed involve some form of a choice operator, though, in general, syntactic restrictions must be placed on the use of the operator in order to ensure that every query has a unique, well-defined result. This project aims to develop a framework within which such operators can be defined formally and which allows their expressive power to be compared. It will demonstrate that syntactic restrictions on the choice operator weaken the expressive power to the point where some feasibly computable properties are no longer definable. It will explore the relationship of choice operators to complexity classes other than polynomial time and also seek to extract general principles that relate the question of the existence of a descriptive characterization of feasibility to another significant open problem: the existence of an efficient algorithm for graph isomorphism.
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.cam.ac.uk