| EPSRC Reference: |
EP/L005654/1 |
| Title: |
Infinite-domain Constraint Satisfaction Problems |
| Principal Investigator: |
Martin, Dr B D |
| Other Investigators: |
|
| Researcher Co-Investigators: |
|
| Project Partners: |
|
| Department: |
School of Science and Technology |
| Organisation: |
Middlesex University |
| Scheme: |
First Grant - Revised 2009 |
| Starts: |
01 April 2014 |
Ends: |
30 September 2015 |
Value (£): |
100,245
|
| EPSRC Research Topic Classifications: |
| Fundamentals of Computing |
|
|
| EPSRC Industrial Sector Classifications: |
|
| Related Grants: |
|
| Panel History: |
| Panel Date | Panel Name | Outcome |
|
24 Oct 2013
|
EPSRC ICT Responsive Mode - Oct 2013
|
Announced
|
|
|
Summary on Grant Application Form |
Constraint Satisfaction Problems (CSPs) provide a powerful framework within which to phrase many computational problems from across Computer Science. In Combinatorics they are known as Homomorphism Problems and in Databases they appear as conjunctive-query containment. CSPs manifest in Artificial Intelligence in the form of temporal and spatial reasoning, and in Computational Linguistics in the guise of tree description languages. In Computational Biology, phylogenetic reconstruction is a CSP, and in Graph Theory it known as H-colouring.
We propose to study the computational complexity of CSPs given by a single constraint language that may have an infinite domain. Research into the finite-domain case is now quite advanced, yet a great many interesting problems, which may not be given as finite-domain CSPs, may be given as infinite-domain CSPs. For example, this is true for most of the CSPs associated with Artificial Intelligence and Computational Linguistics. The computational complexity of most natural finite-domain CSPs is now known, yet many interesting infinite-domain CSPs have open complexity. For example, this is true of the Max Atoms problem, very closely related to Model-checking the mu-calculus, a problem of open complexity from the Verification community. It is also true of the Concatenation problem for free algebras, a problem arising in the Rewriting community. Further, a CSP was recently given that is polynomially equivalent with the elusive problem of Integer factoring. The commonality of structure across CSPs gives hope that we might find generic methods with which to analyse the computational complexity of these diverse problems. We will work on these problems specifically, as well as seeking to map out landscapes of complexity in such areas as the following.
Linear Programming. Linear program feasibility is well-known to be polynomial-time solvable, How much extra expressive power can be added to linear program feasibility while maintaining its tractability?
Integer programming. Integer program feasibility is well-known to be (NP-)hard to solve. How little expressive power does one need to take away to reach tractability?
|
|
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.mdx.ac.uk |