| EPSRC Reference: |
EP/J000078/1 |
| Title: |
Robustly Tractable Constraint Satisfaction Problems |
| Principal Investigator: |
Krokhin, Professor A |
| Other Investigators: |
|
| Researcher Co-Investigators: |
|
| Project Partners: |
|
| Department: |
Engineering and Computing Sciences |
| Organisation: |
Durham, University of |
| Scheme: |
Standard Research |
| Starts: |
19 March 2012 |
Ends: |
18 April 2015 |
Value (£): |
78,524
|
| EPSRC Research Topic Classifications: |
| Fundamentals of Computing |
|
|
| EPSRC Industrial Sector Classifications: |
| No relevance to Underpinning Sectors |
|
|
| Related Grants: |
|
| Panel History: |
| Panel Date | Panel Name | Outcome |
|
13 Jul 2011
|
EPSRC ICT Responsive Mode - July 2011
|
Announced
|
|
|
Summary on Grant Application Form |
The constraint satisfaction problem, or CSP for short, provides a general framework in which it is possible to express, in a natural way, a wide variety of problems from artificial intelligence and computer science. The basic aim in a constraint satisfaction problem is to decide whether there is an assignment of values to a given set of variables, subject to constraints on the values which can be assigned simultaneously to certain specified subsets of variables (decision version, CSP), or to find an assignment satisfying a maximum number of constraints (optimisation version, Max CSP). Nowadays, the CSP is extensively used in theoretical computer science, being a mathematical object with very rich structure that provides an excellent laboratory both for classification methods and for algorithmic techniques. One particular family of CSPs that receives a great amount of attention in complexity theory are the CSPs with a fixed constraint language, i.e. with a restriction on the types of constraints.
A polynomial-time algorithm for a CSP, in general, only needs to tell satisfiable instances from unsatisfiable, i.e. it treats all unsatisfiable instances the same. When can such an algorithm be made to also identify near-misses, i.e. almost satisfiable instances - those where a tiny fraction of constraints can be removed to make the instance satisfiable? We call this type of tractability robust. We plan to develop a new research programme investigating a notion of tractability for CSP with a fixed constraint language that combines in a natural way two very advanced (both technically and conceptually), but so far practically disjoint, directions in the theory of computation: studying classical tractability and approximability of constraint satisfaction problems via algebraic/logical and analytic methods, respectively.
|
|
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: |
|