| 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 |