| EPSRC Reference: |
EP/R034516/1 |
| Title: |
The Complexity of Promise Constraint Satisfaction |
| Principal Investigator: |
Krokhin, Professor A |
| Other Investigators: |
|
| Researcher Co-Investigators: |
|
| Project Partners: |
|
| Department: |
Computer Science |
| Organisation: |
Durham, University of |
| Scheme: |
Standard Research |
| Starts: |
20 June 2018 |
Ends: |
19 December 2021 |
Value (£): |
441,210
|
| 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 |
|
01 Mar 2018
|
EPSRC ICT Prioritisation Panel March 2018
|
Announced
|
|
|
Summary on Grant Application Form |
Why is it that some computational problems admit algorithms that always work fast, i.e. scale up well with the size of data to be processed, while other computational problems are not like this and (appear to) admit only algorithms that scale up exponentially? Answering this question is one of the fundamental goals of theoretical computer science. Computational complexity theory formalises the two kinds of problems as tractable and NP-hard, respectively. So we can rephrase the above question as follows: What kind of inherent mathematical structure makes a computational problem tractable? This very general question is known to be extremely difficult. The Constraint Satisfaction Problem (CSP) and its variants are extensively used towards answering this question for two reasons: on the one hand, the CSP framework is very general and includes a wide variety of computational problems, and on the other hand, this framework has very rich mathematical structure providing an excellent laboratory both for complexity classification methods and for algorithmic techniques.
The so-called algebraic approach to the CSP has been very successful in this quest for understanding tractability. The idea of this approach is that non-trivial algebraic structure (which can viewed roughly as multi-dimensional symmerties) in problem instances leads to tractability, while the absence of such structure leads to NP-hardness. This approach has already provided very deep insights and delivered very strong complexity classification results. It is a common perception that the power of this approach comes largely from the fact that symmetries can be composed, i.e. cascaded, to form another symmetry. The proposed researh will challenge this perception and extend the algebraic approach significantly beyond this seemingly indispensable property. Thus, we will provide further very strong evidence to the thesis that tractable problems posess algebraic structure. We will also apply our new theory to resolve long-standing open questions about some classical NP-hard optimisation problems, specifically how much the optimality demand must be relaxed there to guarantee 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: |
|